QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649967 | #8942. Sugar Sweet 3 | 11d10xy | AC ✓ | 870ms | 8040kb | C++14 | 2.1kb | 2024-10-18 11:54:36 | 2024-10-18 11:54:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
constexpr i64 mod=1000000007;
inline i64 qpow(i64 p,i64 t){
i64 r=1;for(;t;t>>=1,p=p*p%mod)if(t&1)(r*=p)%=mod;
return r;
}
int n,A,B,C,X;
i64 fac[1010],ifac[1010],inv[1010],cat[1010],f[510][510],g[510][510],ans[510];
inline i64 binom(int n,int m){
return m<0||m>n?0:fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
namespace lag{
i64 val[1010],f[1010];
void calc(){
f[1]=1;for(int i=1;i<=n/2;i++){
for(int j=n/2+1;j;j--){
f[j]=(f[j-1]+(mod-i)*f[j])%mod;
}
}
copy_n(ans,n/2+1,val),fill_n(ans,n/2+1,0);
for(int i=0;i<=n/2;i++){
i64 w=val[i]*ifac[i]%mod*ifac[n/2-i]%mod*(n/2-i&1?mod-1:1)%mod,v=0;
for(int k=n/2+1;k;k--){
v=(v*i+f[k])%mod,(ans[k-1]+=v*w)%=mod;
}
}
}
}
void init(int n){
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ifac[0]=1;for(int i=1;i<=n;i++)ifac[i]=ifac[i-1]*inv[i]%mod;
for(int i=1;i<=n/2;i++)cat[i]=binom(i*2,i)*inv[i+1]%mod;
}
void init2(){
f[0][0]=1;
for(int i=1;i<=n/2;i++){
f[i][1]=cat[i];
for(int j=1;j<i;j++)(f[i][1]+=(mod-cat[j])*f[i-j][1])%=mod;
}
for(int i=1;i<=n/2;i++)for(int j=2;j<=i;j++)for(int k=0;k<i;k++)
(f[i][j]+=f[k][j-1]*f[i-k][1])%=mod;
for(int i=0;i<=n/2;i++){
for(int k=0;k<=n/2;k++){
for(int j=i;j>=0;j--){
g[i][k]=(g[i][k]*k+f[i][j]*ifac[j])%mod;
}
}
}
}
int main(){
scanf("%d%d%d%d",&A,&B,&C,&X),n=A+B+C;
if(n&1||max({A,B,C})>n/2)return puts("0"),0;
init(n+2),init2();
for(int a=0;a<=A;a++)for(int b=0;b<=B&&a+b<=n/2;b++){
int c=n/2-a-b;
i64 coef=0;
for(int ab=0;ab<=A-a;ab++){
int ac=A-a-ab,bc=c-ac,cb=b-ab,ba=B-b-bc,ca=c-cb;
(coef+=binom(a,ba)*binom(b,ab)%mod*binom(c,ac))%=mod;
}
for(int k=0;k<=n/2;k++)(ans[k]+=g[a][k]*g[b][k]%mod*g[c][k]%mod*coef)%=mod;
}
lag::calc();
i64 x=0;
for(int k=0;k<=n/2;k++)(x+=qpow(k,X)*ans[k]%mod*fac[k])%=mod;
printf("%lld",x);
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5980kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5980kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 279ms
memory: 7560kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 231ms
memory: 7460kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 6008kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5968kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 222ms
memory: 7576kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 439ms
memory: 7516kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 6ms
memory: 6384kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 750ms
memory: 7860kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 752ms
memory: 8040kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 437ms
memory: 7980kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 870ms
memory: 8036kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 610ms
memory: 7856kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 700ms
memory: 8008kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed