QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#542216 | #8942. Sugar Sweet 3 | ucup-team4504# | AC ✓ | 2195ms | 10076kb | C++14 | 2.7kb | 2024-08-31 23:28:39 | 2024-08-31 23:28:39 |
Judging History
answer
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define MOD 1000000007
using namespace __gnu_pbds;
using namespace std;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int n,A,B,C,x,pw[2010],rev[2010],pwm[1010],val[1010][1010],f[1010],dp[1010][1010];
inline void add1(int &x,int y)
{
x+=y;
if(x>=MOD) x-=MOD;
}
inline void add2(int &x,int y)
{
x+=y;
if(x<0) x+=MOD;
}
inline int my_pow(int x,int y)
{
if(y==0) return 1;
if(y==1) return x;
int res=my_pow(x,y/2);
if(y%2==0) return 1ll*res*res%MOD;
else return 1ll*res*res%MOD*x%MOD;
}
inline int calc(int x,int y)
{
if(x<0||y<0||x<y) return 0;
return 1ll*pw[x]*rev[y]%MOD*rev[x-y]%MOD;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
cin>>A>>B>>C>>x;
if(A>B) swap(A,B);
if(A>C) swap(A,C);
if(B>C) swap(B,C);
n=A+B+C;
if(n%2!=0){
cout<<0<<'\n';
return 0;
}
int M=(A+B+C)/2;
pw[0]=1;
for(int i=1;i<=2*n;i++) pw[i]=1ll*pw[i-1]*i%MOD;
rev[2*n]=my_pow(pw[2*n],MOD-2);
for(int i=2*n-1;i>=0;i--) rev[i]=1ll*rev[i+1]*(i+1)%MOD;
for(int i=0;i<=n;i++){
pwm[i]=my_pow(i,x);
}
for(int i=0;i<=A;i++){
for(int j=0;j<=B;j++) if(i+j<=M){
val[i][j]=0;
for(int a=0;a<=j;a++){
add1(val[i][j],1ll*calc(i,C-M+i+a)*calc(j,a)%MOD*calc(M-i-j,A-i-a)%MOD);
}
}
}
for(int i=0;i<n;i++) f[i+1]=1ll*calc(2*i,i)*my_pow(i+1,MOD-2)%MOD;
dp[0][0]=1;
for(int i=1;i<=M;i++){
dp[i][1]=f[i];
for(int j=2;j<=i;j++){
for(int k=1;k<i;k++) add1(dp[i][j],1ll*f[k]*dp[i-k][j-1]%MOD);
}
}
for(int i=1;i<=M;i++){
for(int j=1;j<=i;j++){
dp[i][j]=1ll*dp[i][j]*rev[j]%MOD;
}
}
int ans=0;
for(int S=0;S<=M;S++){
int Z=M-S;
for(int O=0;O<=S;O++){
int tot=0;
for(int X=max(S-B,0);X<=min(A,S);X++) if(val[X][S-X]){
int Y=S-X;
__int128 res=0;
for(int i=max(O-Y,0);i<=min(X,O);i++){
int j=O-i;
res+=1ll*dp[X][i]*dp[Y][j];
}
add1(tot,1ll*val[X][Y]*(res%MOD)%MOD);
}
for(int k=0;k<=Z;k++){
int cur=1ll*pwm[O+k]*pw[O+k]%MOD;
cur=1ll*cur*dp[Z][k]%MOD;
add1(ans,1ll*cur*tot%MOD);
}
}
}
cout<<ans<<'\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5856kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5908kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 365ms
memory: 8708kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 390ms
memory: 9936kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 103ms
memory: 8668kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 107ms
memory: 7468kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 102ms
memory: 7244kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 3ms
memory: 5976kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 2195ms
memory: 8904kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 2193ms
memory: 9700kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 195ms
memory: 7816kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 210ms
memory: 8516kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 1166ms
memory: 10076kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 1831ms
memory: 10000kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed