JZOJ 5923. 【NOIP2018模拟10.23】Bomb
Description
常数国与 Hack 国近年来战火纷飞。
常数国共有 n 个城市,每两个城市之间均有一条交通线联通。如今常数国遭到 Hack 国的重创,岌岌可危。Hack 国国王小 K 决定轰炸常数国的交通线,对常数国发起最后的攻击。
面对危难之时,常数国国王决定更换首都。在 Hack 国的轰炸结束之后,常数国的领土将会分成若干个联通块。常数国的首都,将会从联通块大小最大的联通块中,随机选择一个城市,作为首都。
小 K 得知了常数国的应对方案之后,他想知道,Hack 国有多少种不同的轰炸方案,使得常数首都所在的联通块大小恰好为 k。两种轰炸方案是不同的,当且仅当一条交通线在一种方案中存在,在另一种方案中被轰炸。由于方案数可能很大,你需要输出方案数对 998,244,353 取模的结果。
Input
从文件bomb.in中读入数据。
共一行,两个整数 n,k ,表示常数国城市的个数与首都所在联通块大小。
Output
输出到文件bomb.out中。
共一行,表示 Hack 国的轰炸方案数对 998,244,353 取模后的结果。
Sample Input
Sample Input 1
3 2
Sample Input 2
5 3
Sample 3
见选手目录下的bomb/bomb3.in与bomb/bomb3.ans。
该组样例的数据范围同第 8 个测试点。
Sample Output
Sample Output1
3
Explanation
3 种方案分别为,仅保留 1 号城市与 2 号城市的交通线,仅保留 2 号城市与3 号城市的交通线,仅保留 1 号城市与 3 号城市的交通线。
Sample Output2
80
Data Constraint
对于 100% 的数据,满足 1 ≤ k ≤ n ≤ 2 × 10 3 。除此之外,对于每个数据点,还满足以下限制。
Solution
-
我们需要灵活地DP!
-
考虑设 表示大小为 的连通图的个数。
-
为了求出 ,我们再设一个 表示大小为 的图的个数。
-
则有:
-
即:
-
那么 就很好求了:
-
注意这些点是有编号的,所以组合数应为 而非 。
-
求出了 我们就更容易求出答案了。
-
设 为大小为 的图的个数,其中这些图中的连通块大小不超过 。
-
于是就有转移:
-
由于 表示的图的连通块大小 ,那么我们又设一个 表示 的。
-
转移即把上面的 换成 。
-
那么答案就是 。
-
时间复杂度 ,用FFT优化可达 。
-
这题的DP方式比较套路,但是如果之前没接触过的话就不是特别好想,需要多积累。
Code
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int N=2005,mo=998244353;
int f[N],g[N],g1[N],h[N],c[N][N];
inline int read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
inline int ksm(int x,int y)
{
int s=1;
while(y)
{
if(y&1) s=(LL)s*x%mo;
x=(LL)x*x%mo;
y>>=1;
}
return s;
}
int main()
{
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
int n=read(),k=read();
for(int i=0;i<=n;i++) c[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
f[0]=g[0]=g1[0]=h[0]=1;
for(int i=1;i<=n;i++)
{
h[i]=ksm(2,i*(i-1)/2);
for(int j=1;j<i;j++)
f[i]=(f[i]+(LL)c[i-1][j-1]*f[j]%mo*h[i-j])%mo;
f[i]=(mo-f[i]+h[i])%mo;
for(int j=1,up=i<k?i:k;j<=up;j++) g[i]=(g[i]+(LL)c[i-1][j-1]*f[j]%mo*g[i-j])%mo;
for(int j=1,up=i<k-1?i:k-1;j<=up;j++) g1[i]=(g1[i]+(LL)c[i-1][j-1]*f[j]%mo*g1[i-j])%mo;
}
printf("%d",(g[n]-g1[n]+mo)%mo);
return 0;
}