QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#905413 | #9777. Balance in All Things | xlwang | AC ✓ | 2574ms | 939860kb | C++14 | 3.8kb | 2025-02-19 10:45:55 | 2025-02-19 10:46:05 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
#define pii pair<int,int>
#define mk make_pair
using namespace std;
inline int read(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
// int t=read();
// while(t--) work();
//}
const int Maxn=4e2+10;
int mod;
inline void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline int Add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int ksm(int x,int y=mod-2){
int sum=1;
while(y){
if(y&1) sum=1ll*sum*x%mod;
y=y/2;x=1ll*x*x%mod;
}return sum;
}
int fac[Maxn<<1],ifac[Maxn<<1];
inline int C(int x,int y){if(x<y || x<0 || y<0) return 0;return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
inline void into(int N){
fac[0]=ifac[0]=1;
fr(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=ksm(fac[N]);
rf(i,N-1,1) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int n,k,m;
inline void init(){
n=read();k=read();m=n*2;mod=read();into(800);
}
int tr1[Maxn][Maxn][Maxn],tr2[Maxn][Maxn][Maxn],f[Maxn][Maxn<<1][Maxn];
int F[Maxn<<1];
int dp1[Maxn],dp2[Maxn][Maxn];
inline void Trans1(){
fr(i,0,n/2) fr(j,0,n/2) dp2[i][j]=0;
fr(pre,0,n) if(dp1[pre]) fr(i,0,n/2) fr(j,0,n/2) add(dp2[i][j],1ll*dp1[pre]*tr1[pre][i][j]%mod);
}
inline void Trans2(){
fr(i,0,n) dp1[i]=0;
fr(i,0,n/2) fr(j,0,n/2) if(dp2[i][j]) fr(nxt,0,n) add(dp1[nxt],1ll*dp2[i][j]*tr2[i][j][nxt]%mod);
}
inline void work(){
memset(f,0,sizeof(f));f[0][0][0]=1;
F[0]=1;for(int i=2;i<=m;i+=2) F[i]=1ll*F[i-2]*(i-1)%mod;
fr(i,0,n) fr(j,0,m) fr(k,0,n){
if(i){
if(j) add(f[i][j][k],1ll*f[i-1][j-1][k]*(j)%mod);
if(k) add(f[i][j][k],1ll*f[i-1][j][k-1]*k%mod);
}
else if(j){
if(j>1) add(f[i][j][k],1ll*f[i][j-2][k]*(j-1)%mod);
if(k) add(f[i][j][k],1ll*f[i][j-1][k-1]*k%mod);
}
}
fr(i,0,n) fr(j,0,i/2) fr(k,0,i/2){
tr1[i][j][k]=1ll*f[i-j*2][m-i*2][i-k*2]*C(i,j*2)%mod*F[j*2]%mod*C(i,k*2)%mod*F[k*2]%mod;
// cout<<i<<' '<<j<<' '<<k<<' '<<tr1[i][j][k]<<endl;
}
memset(f,0,sizeof(f));
fr(i,0,n) fr(j,0,m) fr(k,0,n/2){
if(i==0) f[i][j][k]=1;
else if(j){
add(f[i][j][k],f[i][j-1][k]);
if(j>1) add(f[i][j][k],1ll*f[i-1][j-2][k]*(j-1)%mod);
if(k) add(f[i][j][k],1ll*f[i-1][j-1][k-1]*k%mod);
}
// cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<endl;
}
fr(i,0,n/2) fr(j,0,n/2) fr(k,max(i,j),n){
int x,y;x=n-2*i+j;y=n-2*j+i;
int val=1ll*f[k-i][x][i]%mod*f[k-j][y][j]%mod;
if(n+i+j-k*2<0) val=0;
else val=1ll*val*fac[n+i+j-2*k]%mod;
tr2[i][j][k]=val;
// cout<<i<<' '<<j<<' '<<k<<' '<<val<<endl;
}
dp1[0]=1;
fr(i,1,k){
if(i&1) Trans1();
else Trans2();
}
int ans=0;
if(k%2==0) fr(i,0,n) add(ans,dp1[i]);
else fr(i,0,n/2) fr(j,0,n/2) add(ans,dp2[i][j]);
writeln(ans);
}
signed main(){
// return system("fc output.out output1.out");
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
init();work();
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 65ms
memory: 548664kb
input:
3 1 1000000007
output:
15
result:
ok single line: '15'
Test #2:
score: 0
Accepted
time: 91ms
memory: 642712kb
input:
100 3 1000000007
output:
894710378
result:
ok single line: '894710378'
Test #3:
score: 0
Accepted
time: 57ms
memory: 550856kb
input:
6 6 1000000007
output:
103387851
result:
ok single line: '103387851'
Test #4:
score: 0
Accepted
time: 58ms
memory: 544828kb
input:
2 6 998244353
output:
729
result:
ok single line: '729'
Test #5:
score: 0
Accepted
time: 2574ms
memory: 938384kb
input:
400 20 713862469
output:
561801910
result:
ok single line: '561801910'
Test #6:
score: 0
Accepted
time: 2410ms
memory: 936024kb
input:
397 17 861815723
output:
764050494
result:
ok single line: '764050494'
Test #7:
score: 0
Accepted
time: 2183ms
memory: 931416kb
input:
391 14 189546607
output:
131011086
result:
ok single line: '131011086'
Test #8:
score: 0
Accepted
time: 1962ms
memory: 923480kb
input:
382 11 922402597
output:
58290636
result:
ok single line: '58290636'
Test #9:
score: 0
Accepted
time: 1687ms
memory: 911268kb
input:
370 8 911997731
output:
823449745
result:
ok single line: '823449745'
Test #10:
score: 0
Accepted
time: 1419ms
memory: 895972kb
input:
355 5 708230279
output:
173013324
result:
ok single line: '173013324'
Test #11:
score: 0
Accepted
time: 1558ms
memory: 879300kb
input:
337 19 742344989
output:
592413780
result:
ok single line: '592413780'
Test #12:
score: 0
Accepted
time: 1441ms
memory: 873520kb
input:
334 16 816423319
output:
567577272
result:
ok single line: '567577272'
Test #13:
score: 0
Accepted
time: 1306ms
memory: 868056kb
input:
328 13 463459417
output:
77314092
result:
ok single line: '77314092'
Test #14:
score: 0
Accepted
time: 1148ms
memory: 859984kb
input:
319 10 469180903
output:
94351928
result:
ok single line: '94351928'
Test #15:
score: 0
Accepted
time: 975ms
memory: 848504kb
input:
307 7 240226001
output:
147458009
result:
ok single line: '147458009'
Test #16:
score: 0
Accepted
time: 820ms
memory: 833904kb
input:
292 4 725635439
output:
275908993
result:
ok single line: '275908993'
Test #17:
score: 0
Accepted
time: 853ms
memory: 814940kb
input:
274 18 518962097
output:
200937333
result:
ok single line: '200937333'
Test #18:
score: 0
Accepted
time: 797ms
memory: 812632kb
input:
271 15 765905797
output:
683367155
result:
ok single line: '683367155'
Test #19:
score: 0
Accepted
time: 704ms
memory: 806356kb
input:
265 12 240076537
output:
6822852
result:
ok single line: '6822852'
Test #20:
score: 0
Accepted
time: 622ms
memory: 797648kb
input:
256 9 319057337
output:
9076486
result:
ok single line: '9076486'
Test #21:
score: 0
Accepted
time: 523ms
memory: 786112kb
input:
244 6 257631131
output:
53842743
result:
ok single line: '53842743'
Test #22:
score: 0
Accepted
time: 418ms
memory: 770500kb
input:
229 3 953863681
output:
247424565
result:
ok single line: '247424565'
Test #23:
score: 0
Accepted
time: 54ms
memory: 547220kb
input:
1 20 998244353
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 54ms
memory: 553648kb
input:
8 4 998244353
output:
740255777
result:
ok single line: '740255777'
Test #25:
score: 0
Accepted
time: 57ms
memory: 549012kb
input:
5 20 998244353
output:
725931122
result:
ok single line: '725931122'
Test #26:
score: 0
Accepted
time: 1934ms
memory: 938312kb
input:
400 1 1000000007
output:
705610633
result:
ok single line: '705610633'
Test #27:
score: 0
Accepted
time: 1931ms
memory: 939860kb
input:
400 2 1000000007
output:
917456162
result:
ok single line: '917456162'
Test #28:
score: 0
Accepted
time: 63ms
memory: 544624kb
input:
1 1 1000000007
output:
1
result:
ok single line: '1'
Extra Test:
score: 0
Extra Test Passed