QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #799057 | #7258. Random Walk | peimuda | AC ✓ | 84ms | 122104kb | C++11 | 881b | 2024-12-04 21:15:28 | 2024-12-04 21:15:29 |
Judging History
answer
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
ll m;
ll C[5003][5003];
ll fd[5003],wd[5003];
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin>>n>>m;
C[0][0]=1;
for(int i=0;i<=n;i++) for(int j=0;j<=i;j++)
{
C[i][j]%=m;
C[i+1][j]+=C[i][j];
C[i+1][j+1]+=C[i][j];
}
for(int i=2;i<=n;i+=2) for(int j=0;j<=i;j+=2) fd[i]+=C[i][j]*C[j][j/2]%m*C[i-j][(i-j)/2]%m;
for(int i=2;i<=n;i+=2)
{
fd[i]%=m;
wd[i]=fd[i];
for(int j=2;j<i;j+=2) wd[i]+=m-wd[j]*fd[i-j]%m;
wd[i]%=m;
}
ll ans=0;
ll cmt=1;
for(int i=0;i<n;i++)
{
ans+=m-cmt*wd[n-i]%m*(i+1)%m;
cmt=cmt*4%m;
}
ans+=cmt*(n+1)%m;
cout<<ans%m<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
2 1000000007
output:
44
result:
ok 1 number(s): "44"
Test #2:
score: 0
Accepted
time: 12ms
memory: 27740kb
input:
2015 2000000000
output:
1892319232
result:
ok 1 number(s): "1892319232"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 1335279264
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
2 1849598327
output:
44
result:
ok 1 number(s): "44"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
3 1822889311
output:
224
result:
ok 1 number(s): "224"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
4 1446755913
output:
1068
result:
ok 1 number(s): "1068"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
5 1526239859
output:
4960
result:
ok 1 number(s): "4960"
Test #8:
score: 0
Accepted
time: 84ms
memory: 122104kb
input:
4995 1548830120
output:
950970144
result:
ok 1 number(s): "950970144"
Test #9:
score: 0
Accepted
time: 67ms
memory: 120364kb
input:
4996 1181424399
output:
777518421
result:
ok 1 number(s): "777518421"
Test #10:
score: 0
Accepted
time: 75ms
memory: 120328kb
input:
4997 1715477619
output:
1422350413
result:
ok 1 number(s): "1422350413"
Test #11:
score: 0
Accepted
time: 76ms
memory: 120368kb
input:
4998 1342858071
output:
1282046306
result:
ok 1 number(s): "1282046306"
Test #12:
score: 0
Accepted
time: 70ms
memory: 120520kb
input:
4999 1625711486
output:
685405600
result:
ok 1 number(s): "685405600"
Test #13:
score: 0
Accepted
time: 55ms
memory: 120520kb
input:
5000 1448565595
output:
244248863
result:
ok 1 number(s): "244248863"
Test #14:
score: 0
Accepted
time: 37ms
memory: 94280kb
input:
4325 1647639160
output:
152052616
result:
ok 1 number(s): "152052616"
Test #15:
score: 0
Accepted
time: 79ms
memory: 112064kb
input:
4784 1449656269
output:
62584332
result:
ok 1 number(s): "62584332"
Test #16:
score: 0
Accepted
time: 14ms
memory: 30572kb
input:
2156 1336869678
output:
794572014
result:
ok 1 number(s): "794572014"
Test #17:
score: 0
Accepted
time: 3ms
memory: 10516kb
input:
902 1061020590
output:
502050782
result:
ok 1 number(s): "502050782"
Test #18:
score: 0
Accepted
time: 41ms
memory: 66864kb
input:
3537 1816372580
output:
304447408
result:
ok 1 number(s): "304447408"
Test #19:
score: 0
Accepted
time: 0ms
memory: 8824kb
input:
739 1389312924
output:
82391136
result:
ok 1 number(s): "82391136"
Test #20:
score: 0
Accepted
time: 62ms
memory: 89952kb
input:
4211 1547865075
output:
988813357
result:
ok 1 number(s): "988813357"
Test #21:
score: 0
Accepted
time: 31ms
memory: 65804kb
input:
3506 1605997004
output:
805360668
result:
ok 1 number(s): "805360668"
Test #22:
score: 0
Accepted
time: 7ms
memory: 19640kb
input:
1568 1539239436
output:
1103237896
result:
ok 1 number(s): "1103237896"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
16 1650693494
output:
334199630
result:
ok 1 number(s): "334199630"