QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #415837 | #7365. 东方永夜抄 | juan_123 | 30 | 109ms | 3716kb | C++14 | 870b | 2024-05-21 11:00:49 | 2024-05-21 11:00:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
int qp(int p,int q){
int ans = 1,pro = p;
while(q){
if(q&1)ans = ans*pro%mod;
pro = pro*pro%mod;q>>=1;
}
return ans;
}
int n,k,A;
int s[15],v[15];
int dp[50005];
int val[50005];
signed main(){
cin >> n >> k >> A;
if(k == 0){n--;
int pro = 1;
for(int i = n+1;i<=2*n;i++)pro = pro*i%mod;
for(int i = 1;i<=n+1;i++)pro = pro*qp(i,mod-2)%mod;
cout << pro*qp(A,n)%mod << endl;return 0;
}
for(int i = 1;i<=n;i++)val[i] = A;
for(int i = 1;i<=k;i++){
int s,v;cin >>s >> v;
val[s] = v;
}
dp[1] =1;
for(int i = 2;i<=n;i++){
for(int j = 1;j<i;j++){
dp[i] = (dp[j]*dp[i-j]%mod*val[j]+dp[i])%mod;
}
}
//for(int i = 1;i<=n;i++)cout << dp[i] << ' ';cout << endl;
cout << dp[n] << endl;
return 0;
}/*
20 0 1
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 1ms
memory: 3716kb
input:
729 8 484700931 300 598694964 423 187474540 314 419022666 254 94296176 129 888635716 221 631534755 219 448268736 43 487182990
output:
599001030
result:
ok single line: '599001030'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
761 8 119599063 1 420201406 2 187241921 3 264743797 4 55963177 5 69498518 6 634982960 7 645203226 8 920001009
output:
114033655
result:
ok single line: '114033655'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
840 6 435950652 52 883838625 38 308350134 11 289251261 18 150936562 9 234103210 42 763142373
output:
616532808
result:
ok single line: '616532808'
Subtask #2:
score: 10
Accepted
Test #4:
score: 10
Accepted
time: 66ms
memory: 3516kb
input:
604314 0 881389884
output:
110655526
result:
ok single line: '110655526'
Test #5:
score: 0
Accepted
time: 109ms
memory: 3640kb
input:
1000000 0 715300117
output:
190121322
result:
ok single line: '190121322'
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #6:
score: 0
Time Limit Exceeded
input:
40223 10 593585017 715 890967134 1318 849296717 823 911337804 1918 176598406 2309 108880127 224 458183236 5170 703142296 4283 596249924 7136 89478205 8789 657842023
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%