QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143064 | #2573. Two Permutations | balpoint_pen | WA | 5ms | 19884kb | C++14 | 1.0kb | 2023-08-20 14:41:42 | 2023-08-20 14:41:46 |
Judging History
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'