QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308480#8015. 鸡ucup-team1004100 ✓440ms144952kbC++141.5kb2024-01-20 07:04:122024-01-20 07:04:12

Judging History

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

  • [2024-01-20 07:04:12]
  • 评测
  • 测评结果:100
  • 用时:440ms
  • 内存:144952kb
  • [2024-01-20 07:04:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=3e3+10;
int n,m,mod;
struct zj{
	int cnt,sum;
}f[N][N],g[N][N];
#ifdef DEBUG
ostream& operator << (ostream &out,zj a){
	return out<<'('<<a.cnt<<','<<a.sum<<')';
}
#endif
void add(zj &a,const zj &b,const int &w){
	(a.cnt+=b.cnt)%=mod;
	a.sum=(a.sum+b.sum+1ll*b.cnt*w)%mod;
}
int main(){
	cin>>n>>m>>mod;
	for(int i=0;i<=m;i++)f[0][i]={1,1};
	for(int i=0;i<n;i++){
		zj t={0,0};
		for(int j=m;j>=1;j--){
			add(t,f[i][j],m-j);
			add(t,g[i][j],0);
			add(f[i+2][j-1],t,0);
		}
		t={0,0};
		for(int j=1;j<m;j++){
			add(t,f[i][j],0);
			add(t,g[i][j],0);
			add(g[i+2][j+1],t,m-j-1);
		}
		for(int j=1;j<=m;j++){
			add(f[i+2][j],f[i][j],m-j);
			add(g[i+2][j],g[i][j],m-j);
		}
		for(int j=0;j<=m;j++){
			add(g[i+1][j],f[i][0],m-j);
		}
		for(int j=1;j<=m;j++){
			add(g[i+2][j],f[i][0],m-j);
		}
		add(f[i+1][0],g[i][0],0);
	}
	zj ans={0,0};
	for(int i=1;i<=m;i++){
		add(ans,f[n-1][i],0);
		add(ans,g[n-1][i],0);
	}
	add(ans,f[n][0],0);
	add(ans,f[n-1][0],0);
	cout<<ans.sum<<endl;
	return 0;
}

详细

Test #1:

score: 5
Accepted
time: 1ms
memory: 5660kb

input:

5 5 1004326439

output:

1281

result:

ok 1 number(s): "1281"

Test #2:

score: 5
Accepted
time: 1ms
memory: 5668kb

input:

5 4 1002682123

output:

649

result:

ok 1 number(s): "649"

Test #3:

score: 5
Accepted
time: 2ms
memory: 7772kb

input:

287 1 1003060133

output:

328406329

result:

ok 1 number(s): "328406329"

Test #4:

score: 5
Accepted
time: 0ms
memory: 7880kb

input:

279 1 1004432189

output:

222258837

result:

ok 1 number(s): "222258837"

Test #5:

score: 5
Accepted
time: 0ms
memory: 7852kb

input:

300 1 1005912203

output:

707086810

result:

ok 1 number(s): "707086810"

Test #6:

score: 5
Accepted
time: 0ms
memory: 8032kb

input:

288 5 1003307827

output:

964512417

result:

ok 1 number(s): "964512417"

Test #7:

score: 5
Accepted
time: 1ms
memory: 7680kb

input:

281 5 1008854383

output:

755282155

result:

ok 1 number(s): "755282155"

Test #8:

score: 5
Accepted
time: 0ms
memory: 7664kb

input:

270 5 1007619367

output:

431828317

result:

ok 1 number(s): "431828317"

Test #9:

score: 5
Accepted
time: 0ms
memory: 7900kb

input:

292 5 1002449813

output:

183613546

result:

ok 1 number(s): "183613546"

Test #10:

score: 5
Accepted
time: 2ms
memory: 8128kb

input:

300 5 1005897091

output:

915308166

result:

ok 1 number(s): "915308166"

Test #11:

score: 5
Accepted
time: 1ms
memory: 5860kb

input:

45 50 1009100993

output:

940158800

result:

ok 1 number(s): "940158800"

Test #12:

score: 5
Accepted
time: 1ms
memory: 5956kb

input:

49 50 1001428049

output:

1045902

result:

ok 1 number(s): "1045902"

Test #13:

score: 5
Accepted
time: 1ms
memory: 5780kb

input:

49 50 1007851073

output:

922264698

result:

ok 1 number(s): "922264698"

Test #14:

score: 5
Accepted
time: 1ms
memory: 5820kb

input:

50 50 1005625571

output:

442192770

result:

ok 1 number(s): "442192770"

Test #15:

score: 5
Accepted
time: 0ms
memory: 9032kb

input:

290 300 1005068699

output:

484359497

result:

ok 1 number(s): "484359497"

Test #16:

score: 5
Accepted
time: 0ms
memory: 8736kb

input:

270 300 1003440637

output:

899894137

result:

ok 1 number(s): "899894137"

Test #17:

score: 5
Accepted
time: 7ms
memory: 9416kb

input:

300 300 1008561979

output:

33407754

result:

ok 1 number(s): "33407754"

Test #18:

score: 5
Accepted
time: 440ms
memory: 144668kb

input:

2991 3000 1004658859

output:

167444547

result:

ok 1 number(s): "167444547"

Test #19:

score: 5
Accepted
time: 435ms
memory: 139600kb

input:

2870 3000 1004054173

output:

860666062

result:

ok 1 number(s): "860666062"

Test #20:

score: 5
Accepted
time: 437ms
memory: 144952kb

input:

3000 3000 1009539589

output:

696222334

result:

ok 1 number(s): "696222334"