QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649967#8942. Sugar Sweet 311d10xyAC ✓870ms8040kbC++142.1kb2024-10-18 11:54:362024-10-18 11:54:44

Judging History

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

  • [2024-10-18 11:54:44]
  • 评测
  • 测评结果:AC
  • 用时:870ms
  • 内存:8040kb
  • [2024-10-18 11:54:36]
  • 提交

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