QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #799652 | #7258. Random Walk | cwfxlh | AC ✓ | 97ms | 198516kb | C++14 | 672b | 2024-12-05 16:50:23 | 2024-12-05 16:50:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,MOD,C[5003][5003],f[5003],dp[5003],ans;
signed main(){
ios::sync_with_stdio(false);
cin>>n>>MOD;
for(int i=0;i<=5000;i++)C[i][0]=1;
for(int i=1;i<=5000;i++){
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
}
for(int i=2;i<=n;i+=2){
for(int j=0;j<=i;j+=2)f[i]=(f[i]+C[i][j]*(C[j][j/2]*C[i-j][(i-j)/2]%MOD))%MOD;
}
for(int i=0,j=1;i<=n;i++,j=j*4ll%MOD){
dp[i]=(dp[i]+j)%MOD;
for(int u=i+1;u<=n;u++)dp[u]=(dp[u]-f[u-i]*dp[i])%MOD;
}
for(int i=n,j=1;i>=0;i--,j=j*4ll%MOD)ans=(ans+j*dp[i])%MOD;
ans%=MOD;
ans+=MOD;
ans%=MOD;
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 48ms
memory: 189552kb
input:
2 1000000007
output:
44
result:
ok 1 number(s): "44"
Test #2:
score: 0
Accepted
time: 53ms
memory: 195616kb
input:
2015 2000000000
output:
1892319232
result:
ok 1 number(s): "1892319232"
Test #3:
score: 0
Accepted
time: 38ms
memory: 195364kb
input:
1 1335279264
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 30ms
memory: 195568kb
input:
2 1849598327
output:
44
result:
ok 1 number(s): "44"
Test #5:
score: 0
Accepted
time: 32ms
memory: 195680kb
input:
3 1822889311
output:
224
result:
ok 1 number(s): "224"
Test #6:
score: 0
Accepted
time: 43ms
memory: 195012kb
input:
4 1446755913
output:
1068
result:
ok 1 number(s): "1068"
Test #7:
score: 0
Accepted
time: 36ms
memory: 195024kb
input:
5 1526239859
output:
4960
result:
ok 1 number(s): "4960"
Test #8:
score: 0
Accepted
time: 94ms
memory: 196232kb
input:
4995 1548830120
output:
950970144
result:
ok 1 number(s): "950970144"
Test #9:
score: 0
Accepted
time: 96ms
memory: 195016kb
input:
4996 1181424399
output:
777518421
result:
ok 1 number(s): "777518421"
Test #10:
score: 0
Accepted
time: 88ms
memory: 195976kb
input:
4997 1715477619
output:
1422350413
result:
ok 1 number(s): "1422350413"
Test #11:
score: 0
Accepted
time: 87ms
memory: 195344kb
input:
4998 1342858071
output:
1282046306
result:
ok 1 number(s): "1282046306"
Test #12:
score: 0
Accepted
time: 95ms
memory: 197200kb
input:
4999 1625711486
output:
685405600
result:
ok 1 number(s): "685405600"
Test #13:
score: 0
Accepted
time: 89ms
memory: 197152kb
input:
5000 1448565595
output:
244248863
result:
ok 1 number(s): "244248863"
Test #14:
score: 0
Accepted
time: 72ms
memory: 198516kb
input:
4325 1647639160
output:
152052616
result:
ok 1 number(s): "152052616"
Test #15:
score: 0
Accepted
time: 97ms
memory: 197956kb
input:
4784 1449656269
output:
62584332
result:
ok 1 number(s): "62584332"
Test #16:
score: 0
Accepted
time: 55ms
memory: 198188kb
input:
2156 1336869678
output:
794572014
result:
ok 1 number(s): "794572014"
Test #17:
score: 0
Accepted
time: 47ms
memory: 197532kb
input:
902 1061020590
output:
502050782
result:
ok 1 number(s): "502050782"
Test #18:
score: 0
Accepted
time: 65ms
memory: 197380kb
input:
3537 1816372580
output:
304447408
result:
ok 1 number(s): "304447408"
Test #19:
score: 0
Accepted
time: 38ms
memory: 198084kb
input:
739 1389312924
output:
82391136
result:
ok 1 number(s): "82391136"
Test #20:
score: 0
Accepted
time: 74ms
memory: 198320kb
input:
4211 1547865075
output:
988813357
result:
ok 1 number(s): "988813357"
Test #21:
score: 0
Accepted
time: 69ms
memory: 198212kb
input:
3506 1605997004
output:
805360668
result:
ok 1 number(s): "805360668"
Test #22:
score: 0
Accepted
time: 47ms
memory: 197784kb
input:
1568 1539239436
output:
1103237896
result:
ok 1 number(s): "1103237896"
Test #23:
score: 0
Accepted
time: 38ms
memory: 197328kb
input:
16 1650693494
output:
334199630
result:
ok 1 number(s): "334199630"