Submission #46446

#TimeUsernameProblemLanguageResultExecution timeMemory
46446alex99Calvinball championship (CEOI15_teams)C++14
10 / 100
6 ms1064 KiB
#include <iostream> using namespace std; int N; int A[10005]; int DP[10005]; int Fact[10005], Inv[10005]; const int MOD = 1000007; int Power[10005]; int Nb[10005]; int C[2][1005]; int power(int n, int p) { int sol = 1; while(p) { if(p % 2 == 1) { sol = (1LL * sol * n) % MOD; } p /= 2; n = (1LL * n * n) % MOD; } return sol; } void Read() { cin >> N; for(int i = 1; i <= N; i++) cin >> A[i]; } void precalcFact() { Fact[0] = 1; for(int i = 1; i <= N; i++) Fact[i] = (1LL * Fact[i - 1] * i) % MOD; Inv[N] = power(Fact[N], MOD - 2); for(int i = N - 1; i >= 0; i--) { Inv[i] = (1LL * Inv[i + 1] * (i + 1)) % MOD; } } int Comb(int n, int k) { return C[n][k]; } inline void Add(int& x, int y) { x += y; if(x >= MOD) x -= MOD; } void precalcDP() { DP[0] = 1; for(int i = 1; i <= N; i++) { for(int j = 0; j < i; j++) { Add(DP[i], (1LL * DP[i - 1 - j] * Comb(i - 1, j)) % MOD); } } } void precalcComb() { for(int i = 0; i <= N; i++) C[i][0] = 1; for(int i = 1; i <= N; i++) for(int j = 1; j <= i; j++) { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; if(C[i][j] >= MOD) C[i][j] -= MOD; } } void Solve() { int nb = 1, ans = 1; Nb[1] = 1; for(int i = 2; i <= N; i++) { if(A[i] == Nb[i - 1] + 1) Nb[i] = Nb[i - 1] + 1; else Nb[i] = Nb[i - 1]; } int ind = 0; C[0][0] = 1; for(int i = N; i >= 2; i--, ind = 1 - ind) { if(A[i] == 1) continue; int aux = 0; int pw = 1; if(i < N) { for(int j = N - i; j >= 1; j--) { C[ind][j] = C[1 - ind][j - 1]; Add(C[ind][j], C[1 - ind][j]); } C[ind][0] = 1; int x = N - i; for(int j = 0; j < x; j++) { Add(DP[x], (1LL * DP[x - 1 - j] * C[1 - ind][j]) % MOD); } } for(int j = N - i; j >= 0; j--) { Add(aux, (1LL * C[ind][j] * DP[j] * pw) % MOD); pw = (1LL * pw * Nb[i - 1]) % MOD; } Add(ans, (1LL * aux * (A[i] - 1)) % MOD); } cout << ans << "\n"; } int main() { Read(); precalcFact(); // precalcComb(); precalcDP(); Solve(); //cout << DP[N] << "\n"; return 0; }

Compilation message (stderr)

teams.cpp: In function 'void Solve()':
teams.cpp:78:9: warning: unused variable 'nb' [-Wunused-variable]
     int nb = 1, ans = 1;
         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...