QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #620609 | #7258. Random Walk | dongyc666 | AC ✓ | 115ms | 199000kb | C++14 | 717b | 2024-10-07 19:45:50 | 2024-10-07 19:45:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NR=5e3+10;
int n,p,pw[NR],f[NR],g[NR],c[NR][NR];
void add(int &x,int y){x=(x+y)%p;}
signed main(){
cin>>n>>p;pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*4%p;
for(int i=0;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
for(int i=1;i*2<=n;i++){
for(int j=0;j<=i;j++)add(g[i],c[i*2][j*2]*c[(i-j)*2][i-j]%p*c[j*2][j]);
f[i]=g[i];
for(int j=1;j<i;j++)
add(f[i],-f[j]*g[i-j]);
// cout<<f[i]<<endl;
}
int ans=(n+1)*pw[n]%p;
for(int i=0;i<=n;i++)
for(int j=i+1;j<=n;j++)
if((i&1)==(j&1))add(ans,-pw[i]*pw[n-j]%p*f[(j-i)/2]);
cout<<(ans+p)%p<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3668kb
input:
2 1000000007
output:
44
result:
ok 1 number(s): "44"
Test #2:
score: 0
Accepted
time: 15ms
memory: 83612kb
input:
2015 2000000000
output:
1892319232
result:
ok 1 number(s): "1892319232"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1 1335279264
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 1849598327
output:
44
result:
ok 1 number(s): "44"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 1822889311
output:
224
result:
ok 1 number(s): "224"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 1446755913
output:
1068
result:
ok 1 number(s): "1068"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 1526239859
output:
4960
result:
ok 1 number(s): "4960"
Test #8:
score: 0
Accepted
time: 115ms
memory: 198464kb
input:
4995 1548830120
output:
950970144
result:
ok 1 number(s): "950970144"
Test #9:
score: 0
Accepted
time: 112ms
memory: 198316kb
input:
4996 1181424399
output:
777518421
result:
ok 1 number(s): "777518421"
Test #10:
score: 0
Accepted
time: 104ms
memory: 197848kb
input:
4997 1715477619
output:
1422350413
result:
ok 1 number(s): "1422350413"
Test #11:
score: 0
Accepted
time: 105ms
memory: 198980kb
input:
4998 1342858071
output:
1282046306
result:
ok 1 number(s): "1282046306"
Test #12:
score: 0
Accepted
time: 98ms
memory: 199000kb
input:
4999 1625711486
output:
685405600
result:
ok 1 number(s): "685405600"
Test #13:
score: 0
Accepted
time: 113ms
memory: 198484kb
input:
5000 1448565595
output:
244248863
result:
ok 1 number(s): "244248863"
Test #14:
score: 0
Accepted
time: 85ms
memory: 171880kb
input:
4325 1647639160
output:
152052616
result:
ok 1 number(s): "152052616"
Test #15:
score: 0
Accepted
time: 87ms
memory: 192104kb
input:
4784 1449656269
output:
62584332
result:
ok 1 number(s): "62584332"
Test #16:
score: 0
Accepted
time: 23ms
memory: 87776kb
input:
2156 1336869678
output:
794572014
result:
ok 1 number(s): "794572014"
Test #17:
score: 0
Accepted
time: 4ms
memory: 38600kb
input:
902 1061020590
output:
502050782
result:
ok 1 number(s): "502050782"
Test #18:
score: 0
Accepted
time: 52ms
memory: 142964kb
input:
3537 1816372580
output:
304447408
result:
ok 1 number(s): "304447408"
Test #19:
score: 0
Accepted
time: 0ms
memory: 32480kb
input:
739 1389312924
output:
82391136
result:
ok 1 number(s): "82391136"
Test #20:
score: 0
Accepted
time: 82ms
memory: 167664kb
input:
4211 1547865075
output:
988813357
result:
ok 1 number(s): "988813357"
Test #21:
score: 0
Accepted
time: 47ms
memory: 143056kb
input:
3506 1605997004
output:
805360668
result:
ok 1 number(s): "805360668"
Test #22:
score: 0
Accepted
time: 7ms
memory: 65332kb
input:
1568 1539239436
output:
1103237896
result:
ok 1 number(s): "1103237896"
Test #23:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
16 1650693494
output:
334199630
result:
ok 1 number(s): "334199630"