QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717740 | #8942. Sugar Sweet 3 | c20230201 | AC ✓ | 1197ms | 7736kb | C++20 | 2.6kb | 2024-11-06 18:51:04 | 2024-11-06 18:51:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> poly;
const ll mo=1e9+7;
ll n;
ll f[505][505], g[505][505], ans[505], ans2[505];
ll V[505], fac[1005], ifac[1005];
ll C(ll n,ll m) {
if(n<m||n<0||m<0) return 0;
return fac[n]*ifac[m]%mo*ifac[n-m]%mo;
}
ll qpow(ll a,ll p) {
ll res=1;
while(p) {
if(p&1) res=res*a%mo;
p>>=1, a=a*a%mo;
}
return res;
}
poly mul(poly a,poly b) {
poly c(a.size()+b.size()-1,0);
for(ll i=0;i<a.size();i++) {
for(ll j=0;j<b.size();j++) {
(c[i+j]+= a[i]*b[j]%mo)%=mo;
}
}
return c;
}
poly div(poly a,ll c) {
poly b(a.size()-1,0);
for(ll i=b.size()-1;i>=0;i--) {
b[i]=a[i+1];
(a[i]+= c*b[i]%mo)%=mo;
}
return b;
}
void lglr() {
poly t={1};
for(ll i=0;i<=n/2;i++) t=mul(t,poly{(mo-i)%mo,1});
for(ll i=0;i<=n/2;i++) {
poly t2=div(t,i);
ll coef=ifac[i]%mo*ifac[n/2-i]%mo*((n/2-i)&1?mo-1:1)%mo;
for(ll j=0;j<=n/2;j++) (ans2[j]+= coef*ans[i]%mo*t2[j]%mo)%=mo;
}
return ;
}
int main() {
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll u,v,w,x; cin>>u>>v>>w>>x;
n=u+v+w;
if(n&1) {
cout<<"0\n";
return 0;
}
fac[0]=1;
for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n],mo-2);
for(ll i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mo;
for(ll i=1;i<=n/2;i++) V[i]=(C(i*2-2,i-1)-C(i*2-2,i-2)+mo)%mo;
f[0][0]=1;
for(ll i=1;i<=n/2;i++) {
for(ll j=i;j<=n/2;j++) {
for(ll k=1;k<=j;k++) {
(f[j][i]+= f[j-k][i-1]*V[k]%mo)%=mo;
}
}
}
for(ll i=0;i<=n/2;i++) {
for(ll j=0;j<=n/2;j++) (f[i][j]*= ifac[j])%=mo;
for(ll v=0;v<=n/2;v++) {
for(ll j=0,pw=1;j<=n/2;j++,pw=pw*v%mo) (g[i][v]+= pw*f[i][j]%mo)%=mo;
}
}
for(ll x=0;x<=n/2;x++) {
for(ll y=0;x+y<=n/2;y++) {
ll coef=0;
ll z=n/2-x-y;
for(ll a=0;a<=x;a++) {
ll c=y+z+a-v;
ll b=x+y+z-a-w;
(coef+= C(x,a)*C(y,b)%mo*C(z,c)%mo)%=mo;
}
if(!coef) continue;
for(ll i=0;i<=n/2;i++) (ans[i]+= g[x][i]*g[y][i]%mo*g[z][i]%mo*coef%mo)%=mo;
}
}
lglr();
ll sum=0;
for(ll i=1;i<=n/2;i++) (sum+= qpow(i,x)*ans2[i]%mo*fac[i]%mo)%=mo;
cout<<sum<<'\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5832kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 537ms
memory: 7496kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 421ms
memory: 7380kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 447ms
memory: 7524kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 451ms
memory: 7244kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 457ms
memory: 7228kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 8ms
memory: 6076kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 1174ms
memory: 7704kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 1197ms
memory: 7736kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 881ms
memory: 7712kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 880ms
memory: 7656kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 1089ms
memory: 7728kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 1164ms
memory: 7644kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed