QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143064#2573. Two Permutationsbalpoint_penWA 5ms19884kbC++141.0kb2023-08-20 14:41:422023-08-20 14:41:46

Judging History

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

  • [2023-08-20 14:41:46]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:19884kb
  • [2023-08-20 14:41:42]
  • 提交

answer

/*
    Author: YZB
    Problem:
    Time:
*/
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7) 
#define rep(_i_,_l_,_r_) for(int _i_=_l_;_i_<=_r_;_i_++)
//#define FILE
using namespace std;
int dp[2][105][10005];
signed main(){
#ifdef FILE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	dp[0][0][0]=1;
	int p=0,c1,c2,c0;
	for(int i=n;i>=1;i--){
		p^=1;
		memset(dp[p],0,sizeof dp[p]);
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n*n;k++){
				if(!dp[p^1][j][k])continue;
				c1=j,c2=((n-i)-j),c0=n-c1-c2;
				dp[p][j][k+i]+=dp[p^1][j][k]*c0%mod;
				dp[p][j][k+i]%=mod;
				if(j>=1){
					dp[p][j-1][k]+=dp[p^1][j][k]*((c1*c1)%mod)%mod;
					dp[p][j-1][k]%=mod;
				}
				dp[p][j][k+i]+=dp[p^1][j][k]*c1%mod*c0*2ll%mod;
				dp[p][j][k+i]%=mod;
				if(j+1<=n){
					dp[p][j+1][k+2*i]+=dp[p^1][j][k]*(c0*(c0-1)%mod)%mod;
					dp[p][j+1][k+2*i]%=mod;
				}
			}
		}
	}
	cout<<dp[p][0][m]<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 19832kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 19832kb

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 0
Accepted
time: 1ms
memory: 19876kb

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

score: -100
Wrong Answer
time: 5ms
memory: 19884kb

input:

4 14

output:

288

result:

wrong answer 1st numbers differ - expected: '96', found: '288'