QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722980 | #8942. Sugar Sweet 3 | yz_ly | AC ✓ | 1163ms | 12564kb | C++14 | 3.8kb | 2024-11-07 20:47:29 | 2024-11-07 20:47:29 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
inline void write(ll k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
write(k/10);
putchar(k%10+'0');
}
/*
记n=U+V+W
当n为奇数的时候答案为0,因为一定消不完
长度为2*i的括号序列数量是卡特兰数第i项
预处理f[i][j]表示括号序列长度为2*i,有j个地方被消空的方案数,用卡特兰数计算就行,枚举最后一段和为0的,去掉边上一对,中间就是一个随意配对的卡特兰数
我们将牌堆中被消除的牌看成左括号,其它的看成右括号
枚举i,j表示小u,小v的牌作为左括号的次数,小w的次数就是n/2-i-j
第一部分的贡献就是左右括号如何配对
因为同一人的右括号不能与同一人的左括号配对,所以我们枚举一个k表示有多少个小u的右括号与小v的左括号配对,然后我们能够算出所有配对的情况
如小w的右括号与小v的左括号配对的个数就是j-k....,那么这一部分的贡献就用组合数很简单的算完了
第二部分就是有多少个配对完,并且如何排列
很暴力的枚举p1,p2,p3表示小u,小v,小w有多少个和为0的时刻,此时的方案数就是f[i][p1]*f[j][p2]*f[n/2-i-j][p3]*(p1+p2+p3)!/p1!/p2!/p3!
但是你发现这个东西相当于三个多项式f_i=sum(f[i][j]/j!*x^j),点值的横坐标取0~n/2就行,就直接对应点值相乘再插值回去就行了
两部分相乘即可
*/
const ll mod=1e9+7;
int n,U,V,W,x;
ll jc[2005],inv[2005],inv1[2005],dp[1005][1005],f[1005][1005],g[1005],ans[1005],res[1005],res1[1005],h[1005];
ll C(ll n,ll m){
if(n<m||n<0||m<0)
return 0;
return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
ll F(ll n){
return C(2*n,n)*inv1[n+1]%mod;
}
ll power(ll a,ll b){
ll sum=1,k=a;
while(b){
if(b&1ll)
sum=sum*k%mod;
k=k*k%mod;
b>>=1ll;
}
return sum;
}
void solve(ll *y){
for(int i=0;i<=n/2+1;i++){
res[i]=0;
}
res[0]=1;
for(int i=0;i<=n/2;i++){
for(int j=n/2+1;j>=0;j--){
res[j]=((j?res[j-1]:0)-i*res[j]%mod)%mod;
}
}
for(int i=0;i<=n/2;i++){
ll val=inv[i]*inv[n/2-i]%mod*((n/2-i)&1?-1:1)%mod;
for(int j=0;j<=n/2+1;j++){
res1[j]=-(res[j]-(j?res1[j-1]:0))*inv1[i]%mod;
}
for(int j=0;j<=n/2+1;j++){
h[j]=(h[j]+y[i]*val%mod*res1[j]%mod)%mod;
}
}
for(int i=0;i<=n/2;i++){
y[i]=h[i];
}
}
int main(){
U=read();
V=read();
W=read();
x=read();
n=U+V+W;
if(n&1){
write(0);
return 0;
}
jc[0]=inv[0]=inv[1]=jc[1]=inv1[1]=1;
for(int i=2;i<=2e3;i++){
jc[i]=jc[i-1]*i%mod;
inv1[i]=inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=2;i<=2e3;i++){
inv[i]=inv[i]*inv[i-1]%mod;
}
dp[0][0]=1;
for(int i=1;i<=n/2;i++){
for(int j=1;j<=i;j++){
for(int k=0;k<i;k++){
dp[i][j]=(dp[i][j]+dp[k][j-1]*F(i-k-1)%mod)%mod;
}
}
for(int j=0;j<=n/2;j++){
for(int k=i;k>=0;k--){
f[i][j]=(f[i][j]*j%mod+dp[i][k]*inv[k]%mod)%mod;
}
}
}
for(int j=0;j<=n/2;j++){
f[0][j]=(f[0][j]*j%mod+dp[0][0]*inv[0]%mod)%mod;
}
for(int i=0;i<=U;i++){
for(int j=0;j<=V&&j+i<=n/2;j++){
int p=n/2-i-j;
ll sum=0;
for(int k=max(j-(W-p),0);k<=U-i&&k<=j;k++){
sum=(sum+C(j,k)*C(i,W-p-(j-k))%mod*C(p,U-i-k)%mod)%mod;
}
for(int k=0;k<=n/2;k++){
ans[k]=(ans[k]+f[i][k]*f[j][k]%mod*f[n/2-i-j][k]%mod*sum%mod)%mod;
}/*本来是要对k=0~n/2都做一次插值的,但是f(a)+f(b)=f(a+b),所以对总和做一次就行了,点值可以直接求*/
}
}
solve(ans);
ll ans1=0;
for(int k=0;k<=n/2;k++){
ans1=(ans1+ans[k]*power(k,x)%mod*jc[k]%mod)%mod;
}
write((ans1+mod)%mod);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5748kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 492ms
memory: 9716kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 396ms
memory: 9244kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 416ms
memory: 9616kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 415ms
memory: 10584kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 597ms
memory: 10288kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 5ms
memory: 6152kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 1157ms
memory: 11748kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 1163ms
memory: 12564kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 817ms
memory: 12240kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 1155ms
memory: 11972kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 1034ms
memory: 12508kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 1119ms
memory: 11916kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed