QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717740#8942. Sugar Sweet 3c20230201AC ✓1197ms7736kbC++202.6kb2024-11-06 18:51:042024-11-06 18:51:06

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 18:51:06]
  • 评测
  • 测评结果:AC
  • 用时:1197ms
  • 内存:7736kb
  • [2024-11-06 18:51:04]
  • 提交

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,我给组数据试试?

详细

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