QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276812#7258. Random WalkQingyuAC ✓165ms199404kbC++231.3kb2023-12-06 11:03:242023-12-06 11:05:02

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 11:05:02]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:165ms
  • 内存:199404kb
  • [2023-12-06 11:03:24]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3584kb
  • [2023-12-06 11:03:24]
  • 提交

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"