#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int mul(int x,int y){return (ll)x*y%mod;}
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
void ckadd(int&x,int y){x=add(x,y);}
const int N=605;
const int M=N*2;
int F[M],I[M],a[N],dp[N][N];
int binom(int n,int k){return mul(F[n],mul(I[k],I[n-k]));}
int main(){
F[0]=1;for(int i=1;i<M;i++)F[i]=mul(F[i-1],i);
I[1]=1;for(int i=2;i<M;i++)I[i]=mul(sub(mod,mod/i),I[mod%i]);
I[0]=1;for(int i=2;i<M;i++)I[i]=mul(I[i],I[i-1]);
int n;scanf("%i",&n);
for(int i=1;i<=n;i++)scanf("%i",&a[i]);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=a[i]-i;j++){
dp[i][j]=mul(dp[i-1][j],j-i+1);
for(int k=1;k<=j;k++){
ckadd(dp[i][j],mul(binom(k*2,k),mul(binom(a[i]-i-j+k,k),mul(F[k],dp[i-1][j-k]))));
}
}
}
int ans=dp[n][n];
for(int i=1;i<=n;i++)ans=mul(ans,(mod+1)/2);
printf("%i\n",ans);
return 0;
}
Compilation message
ruins3.cpp: In function 'int main()':
ruins3.cpp:17:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n;scanf("%i",&n);
~~~~~^~~~~~~~~
ruins3.cpp:18:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%i",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
512 KB |
Output is correct |
| 12 |
Correct |
1 ms |
512 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
512 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
512 KB |
Output is correct |
| 12 |
Correct |
1 ms |
512 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
512 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
2 ms |
512 KB |
Output is correct |
| 21 |
Correct |
68 ms |
1784 KB |
Output is correct |
| 22 |
Correct |
39 ms |
1784 KB |
Output is correct |
| 23 |
Correct |
62 ms |
1784 KB |
Output is correct |
| 24 |
Correct |
85 ms |
1784 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
46 ms |
1784 KB |
Output is correct |
| 27 |
Correct |
13 ms |
1152 KB |
Output is correct |
| 28 |
Correct |
5 ms |
1792 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
1116 ms |
1844 KB |
Output is correct |
| 31 |
Correct |
848 ms |
1784 KB |
Output is correct |
| 32 |
Correct |
921 ms |
1964 KB |
Output is correct |
| 33 |
Correct |
1032 ms |
1784 KB |
Output is correct |
| 34 |
Correct |
745 ms |
2040 KB |
Output is correct |
| 35 |
Correct |
915 ms |
1784 KB |
Output is correct |
| 36 |
Correct |
1038 ms |
1720 KB |
Output is correct |
