Reduce to One
Problem statement – https://www.codechef.com/MAY19B/problems/REDONE
It doesn’t matter whichever element we choose, answer will be same. I have come to this conclusion after observation on few testcases. Formal proof will be added later.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,s,e) for(int i=s; i<=e; i++)
#define WL(t) while(t--)
#define MAXN 1000010
#define MOD 1000000007
int dp[MAXN];
int n;
class fastio {
public:
fastio() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
}
} __fastio;
void precalculate() {
dp[1] = 1;
FOR(i,2,MAXN) {
dp[i] = (dp[i-1] * i + dp[i-1] + i) % MOD;
}
}
void solve() {
cin >> n;
cout << dp[n] << endl;
}
int32_t main() {
__fastio;
precalculate();
int t; cin >> t;
WL(t) {
solve();
}
return 0;
}
Home of Code 