QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#572487 | #8942. Sugar Sweet 3 | yyyyxh | AC ✓ | 293ms | 8596kb | C++14 | 2.6kb | 2024-09-18 14:54:21 | 2024-09-18 14:54:21 |
Judging History
answer
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1003,M=503,P=1000000007;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
int A,B,C,n,ex;
int fac[N],fiv[N];
int cb[N][N],pw[M][M];
int f[M],dp[M][M],arr[M][M];
int res[M];__int128 seq[M];
int getc(int u,int v){
if(v>u||v<0) return 0;
return cb[u][v];
}
int calc(int x,int y,int z){
if(x>A||y>B||z>C) return 0;
// A -> B i
// A -> C x-i
// B -> C C-z-x+i
// B -> A y-C+z+x-i
// C -> B B-y-i
// C -> A z-B+y+i
__int128 coe=0;
for(int i=0;i<=B-y&&i<=x;++i) coe+=(__int128)getc(x,i)*getc(y,C-z-x+i)*getc(z,B-y-i);
return coe%P;
}
int poly[N],sz;
int dpoly[N];
void prod(int v){
for(int i=++sz;i;--i) poly[i]=(poly[i-1]+(ll)poly[i]*(P-v))%P;
}
void iprod(int v){
if(v){
int iv=qp(P-v);
for(int i=0;i<sz;++i) dpoly[i]=(ll)(poly[i]-dpoly[i-1]+P)*iv%P;
}
else{
for(int i=0;i<sz;++i) dpoly[i]=poly[i+1];
}
}
int main(){
A=read(),B=read(),C=read();n=A+B+C;ex=read();
if(n&1){puts("0");return 0;}
fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%P;
fiv[n]=qp(fac[n]);
for(int i=n;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
for(int i=0;i<=n;++i)
for(int j=0;j<=i;++j) cb[i][j]=(ll)fac[i]*fiv[j]%P*fiv[i-j]%P;
n>>=1;
for(int i=1;i<=n;++i){
f[i]=getc(2*i-2,i-1)-getc(2*i-2,i);
if(f[i]<0) f[i]+=P;
}
dp[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j){
__int128 cur=0;
for(int x=1;x<=i;++x) cur+=(ll)dp[i-x][j-1]*f[x];
dp[i][j]=cur%P;
}
for(int x=1;x<=n;++x){
pw[x][0]=1;
for(int i=1;i<=n;++i) pw[x][i]=(ll)pw[x][i-1]*x%P;
}
for(int x=0;x<=n;++x) arr[0][x]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j) dp[i][j]=(ll)dp[i][j]*fiv[j]%P;
for(int x=1;x<=n;++x){
__int128 cur=0;
for(int j=1;j<=i;++j) cur+=(ll)pw[x][j]*dp[i][j];
arr[i][x]=cur%P;
}
}
for(int a=0;a<=A;++a)
for(int b=0;b<=B;++b){
int c=n-a-b;
int sum=calc(a,b,c);
if(!sum) continue;
for(int i=0;i<=n;++i) seq[i]+=(__int128)arr[a][i]*arr[b][i]*arr[c][i]%P*sum;
}
poly[sz=1]=1;
for(int i=1;i<=n;++i) prod(i);
for(int i=0;i<=n;++i){
iprod(i);
int val=seq[i]%P*fiv[i]%P*fiv[n-i]%P;
if((n^i)&1) val=P-val;
for(int x=0;x<=n;++x) res[x]=(res[x]+(ll)dpoly[x]*val)%P;
}
int ans=0;
for(int i=1;i<=n;++i) ans=(ans+(ll)qp(i,ex)*res[i]%P*fac[i])%P;
printf("%d\n",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1484kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1364kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 101ms
memory: 8088kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 96ms
memory: 7128kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 1476kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 46ms
memory: 7544kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 42ms
memory: 7920kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 60ms
memory: 7596kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 0ms
memory: 6020kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 293ms
memory: 8588kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 292ms
memory: 8592kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 96ms
memory: 8524kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 125ms
memory: 8592kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 237ms
memory: 8532kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 284ms
memory: 8596kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5764kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed