停课了 好起来了
# 题面
> Linked AtCoder TENKA2019-D
点击展开/折叠 题面
有 $n$ 个正整数，把它们分为 $R,G,B$ 三个集合（每个数恰好在一个集合中且每个集合都不空）；求有多少种分法使得 $sum(R),sum(G),sum(B)$ 可以构成三角形。
$n\le300$，所有数字不超过 $300$。
# 解析
显然要DP……
要求构成三角形，则有最长边小于两短边之和，但是在这个限制下，很难设计出状态能够表示最长边。正难则反，求“最长边大于等于两短边之和”的方案数。
因为三边之和 $S$ 固定，两短边之和不超过 $\lfloor\frac S2\rfloor$。于是设计状态 $f_{i,j}$ 表示前 $i$ 个数字中选出一些分为两组（两个较短边）的方案数，转移也比较简单，要么不选（$f_{i-1,j}$）要么分到两组中的一个（$2\times f_{i-1,j-a_i}$）。
但是这样计算有些问题，会分出某一个集合是空集的情况，只要有一种 $sum(C)=j$ 的方案，就会对应两种（$A=C,B=\varnothing$ 和 $A=\varnothing,B=C$）非法情况。于是再做一个DP，$g_{i,j}$ 表示前 $i$ 个数选一些数使得和为 $j$ 的方案数。
$f_{n,i}-2\times g_{n,i}$ 则是两短边之和为 $i$ 的方案数，再从三个集合中选出一个作为最长边，即 $3\times(f_{n,i}-2\times g_{n,i})$；于是可以计算得到在所有集合非空的方案中非法方案数的数量 $d$：
最后就剩求总方案数了。注意到由于“非法方案数”求的是在所有集合非空的前提下的非法方案，总方案也应保证集合非空。
相当于把 $n$ 个有区别的数分到 $3$ 个有区别的集合中使得集合非空的方案数。可以用第二类斯特林数（把 $n$ 个有标号球放入 $m$ 个无标号盒子里且盒子不空）。最后答案为 $3!\times S(n,3)-d$。
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ci const int &
const int N=305,MOD=998244353;
inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}
const int INV2=Pow(2,MOD-2);
int n;
int num[N],f[2][N*N],g[2][N*N],w[N][4];
inline int Read(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
int main(){
Read(n);
w[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=3;j++)
w[i][j]=Add(w[i-1][j-1],Mul(j,w[i-1][j]));
int S=0;
for(int i=1;i<=n;i++) S+=Read(num[i]);
S>>=1;
f[0][0]=g[0][0]=1;
for(int i=1;i<=n;i++){
int I=i&1,J=!I;
for(int j=0;j<=S;j++) f[I][j]=f[J][j],g[I][j]=g[J][j];
for(int j=num[i];j<=S;j++){
f[I][j]=Add(f[I][j],Mul(2,f[J][j-num[i]]));
g[I][j]=Add(g[I][j],g[J][j-num[i]]);
}
}
int del=0;
for(int i=1;i<=S;i++){
int thi=Mul(f[n&1][i],INV2);
thi=Sub(thi,g[n&1][i]);
del=Add(del,Mul(thi,6));
}
int ans=Mul(w[n][3],6);
printf("%d\n",Sub(ans,del));
return 0;
}
|
THE END
Thanks for reading!
> Linked 夏日已所剩无几-网易云