Submission #859001

#TimeUsernameProblemLanguageResultExecution timeMemory
859001Tenis0206Calvinball championship (CEOI15_teams)C++11
20 / 100
1048 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e4; const int Mod = 1e9 + 7; int n; int v[nmax + 5]; int fact[nmax + 5], invfact[nmax + 5]; int dp[nmax + 5]; int lgput(int a, int b) { int p = 1; while(b) { if(b % 2 == 0) { b/=2; a = 1LL * a * a % Mod; } else { --b; p = 1LL * p * a % Mod; } } return p; } int invmod(int x) { return lgput(x,Mod-2); } int comb(int n, int k) { return 1LL * fact[n] * invfact[k] % Mod * invfact[n - k] % Mod; } void precalc() { fact[0] = 1; for(int i=1;i<=nmax;i++) { fact[i] = 1LL * fact[i - 1] * i % Mod; } invfact[nmax] = invmod(fact[nmax]); for(int i=nmax-1;i>=0;i--) { invfact[i] = 1LL * invfact[i + 1] * (i + 1) % Mod; } } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n; precalc(); for(int i=1;i<=n;i++) { cin>>v[i]; } dp[0] = 1; for(int i=0;i<=n;i++) { for(int nr=1;i+nr<=n;nr++) { dp[i + nr] += 1LL * dp[i] * comb(i + nr - 1, nr - 1) % Mod; dp[i + nr] %= Mod; } } int Max = 0; long long rez = 0; for(int i=1;i<=n;i++) { if(v[i]==1) { Max = max(Max, v[i]); continue; } for(int nr=0;i+nr<=n;nr++) { rez += 1LL * dp[nr] * comb(n - i, nr) % Mod * lgput(Max, n - i - nr) % Mod * (v[i] - 1) % Mod; rez %= Mod; } Max = max(Max, v[i]); } rez = (rez + 1) % Mod; cout<<rez<<'\n'; return 0; }
#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...