Day: June 13, 2019

Codechef May Long Challenge 2019

~ Suraj Shaw ~ Leave a comment

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;
}