QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276812 | #7258. Random Walk | Qingyu | AC ✓ | 165ms | 199404kb | C++23 | 1.3kb | 2023-12-06 11:03:24 | 2023-12-06 11:05:02 |
Judging History
answer
#include <string.h>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
ll MOD;
ll comb[5010][5010];
ll dp[5010],dp2[5010];
ll power[5010];
int main(void){
int N,i,j;
cin >> N >> MOD;
REP(i,N+1) REP(j,i+1){
if(j == 0 || j == i) comb[i][j] = 1;
else comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
}
power[0] = 1;
for(i=1;i<=N;i++) power[i] = power[i-1] * 4 % MOD;
REP(i,N+1) REP(j,N+1) if(2*(i+j) <= N) dp[2*(i+j)] = (dp[2*(i+j)] + comb[2*i+2*j][i] * comb[i+2*j][i] % MOD * comb[2*j][j]) % MOD;
REP(i,N+1){
dp2[i] = dp[i];
for(j=1;j<i;j++) dp2[i] = (dp2[i] - dp2[j] * dp[i-j] % MOD + MOD) % MOD;
}
ll ans = (N + 1) * power[N] % MOD;
for(i=1;i<=N;i++) ans = (ans - dp2[i] * power[N-i] % MOD * (N-i+1) % MOD + MOD) % MOD;
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
input:
2 1000000007
output:
44
result:
ok 1 number(s): "44"
Test #2:
score: 0
Accepted
time: 28ms
memory: 81692kb
input:
2015 2000000000
output:
1892319232
result:
ok 1 number(s): "1892319232"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
1 1335279264
output:
8
result:
ok 1 number(s): "8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 1849598327
output:
44
result:
ok 1 number(s): "44"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
3 1822889311
output:
224
result:
ok 1 number(s): "224"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
4 1446755913
output:
1068
result:
ok 1 number(s): "1068"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 1526239859
output:
4960
result:
ok 1 number(s): "4960"
Test #8:
score: 0
Accepted
time: 165ms
memory: 198492kb
input:
4995 1548830120
output:
950970144
result:
ok 1 number(s): "950970144"
Test #9:
score: 0
Accepted
time: 159ms
memory: 198644kb
input:
4996 1181424399
output:
777518421
result:
ok 1 number(s): "777518421"
Test #10:
score: 0
Accepted
time: 138ms
memory: 198408kb
input:
4997 1715477619
output:
1422350413
result:
ok 1 number(s): "1422350413"
Test #11:
score: 0
Accepted
time: 139ms
memory: 199404kb
input:
4998 1342858071
output:
1282046306
result:
ok 1 number(s): "1282046306"
Test #12:
score: 0
Accepted
time: 147ms
memory: 198420kb
input:
4999 1625711486
output:
685405600
result:
ok 1 number(s): "685405600"
Test #13:
score: 0
Accepted
time: 154ms
memory: 199076kb
input:
5000 1448565595
output:
244248863
result:
ok 1 number(s): "244248863"
Test #14:
score: 0
Accepted
time: 109ms
memory: 173764kb
input:
4325 1647639160
output:
152052616
result:
ok 1 number(s): "152052616"
Test #15:
score: 0
Accepted
time: 148ms
memory: 192064kb
input:
4784 1449656269
output:
62584332
result:
ok 1 number(s): "62584332"
Test #16:
score: 0
Accepted
time: 32ms
memory: 87884kb
input:
2156 1336869678
output:
794572014
result:
ok 1 number(s): "794572014"
Test #17:
score: 0
Accepted
time: 3ms
memory: 38620kb
input:
902 1061020590
output:
502050782
result:
ok 1 number(s): "502050782"
Test #18:
score: 0
Accepted
time: 77ms
memory: 141012kb
input:
3537 1816372580
output:
304447408
result:
ok 1 number(s): "304447408"
Test #19:
score: 0
Accepted
time: 3ms
memory: 34392kb
input:
739 1389312924
output:
82391136
result:
ok 1 number(s): "82391136"
Test #20:
score: 0
Accepted
time: 121ms
memory: 167596kb
input:
4211 1547865075
output:
988813357
result:
ok 1 number(s): "988813357"
Test #21:
score: 0
Accepted
time: 93ms
memory: 140856kb
input:
3506 1605997004
output:
805360668
result:
ok 1 number(s): "805360668"
Test #22:
score: 0
Accepted
time: 16ms
memory: 65200kb
input:
1568 1539239436
output:
1103237896
result:
ok 1 number(s): "1103237896"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
16 1650693494
output:
334199630
result:
ok 1 number(s): "334199630"