【2023NOI模拟赛08】节日 做题记录

罗曼诺夫统一了全世界，开创了人类的新纪元。

为了让子民们和罗曼诺夫一样卷，罗曼诺夫决定把一年设为 $D$ 天，当中只有一天放假，也就是罗曼诺夫的生日。

然而，罗曼诺夫飞升之后，他的继承人却误解了罗曼诺夫的意思，没能继承罗曼诺夫的卷志。每一个继承人登基时都会把自己的生日设为假日，并且如果存在一天，它前后都是假日，那么这天也会被自动设为假日。 把 $D$ 天看做一个环，也就是说第一天和第 $D$ 天相邻。

我们假设每年会换一个继承人，所有人的生日都独立在 $D$ 天中随机。

工作日逐渐减少，人民无所事事。当一年之中只剩下小于等于 $K$ 天工作日的时候，国家终于崩溃了。

天上的罗曼诺夫预料到了这一切。请你帮他算一下，在亡国之前，每一年的权值之和的期望。

定义一年的权值为这一年中假期的总天数的 $t$ 次方。

更加严谨的描述：从初始全都不是假日开始，令计数器 $cnt=0$ ，一直执行以下操作：

• 在 $D$ 天中均匀随机一天，把它设为假日。
• 把两边都是假日的日期也变成假日。
• 设此时假日的个数为 s 。如果 $D−s\le K$ 那么退出循环，否则 $cnt\leftarrow^+ s^t$ 并返回第一步。

求 $cnt$ 的期望，对 $998244353$ 取模。

$0\le K<D\le 2000,0\le t\le 10^8$。

注意到共有 $i$ 天假日时有 $j$ 段独立的连续假日段所有情况的概率都是一样的，所以可以设 $dp_{i,j}$ 表示共有 $i$ 天假日时，有 $j$ 段独立的连续假日段的所有情况的总概率，并且暂时先不考虑选择的假日之前被选过的情况。

设 $\operatorname{calc}(i,j)$ 表示有 $i$ 天假日，分成 $j$ 段独立的连续假日段的方案数，即 $dp_{i,j}$ 中共有多少种情况，显然可以用插板法快速求出，那么每种情况的概率即为 $ech=\frac{dp_{i,j}}{\operatorname{calc}(i,j)}$。

转移考虑下一次选择作为假日的是哪一天，首先所有转移的方案数和为 $all=(D-i)\times \operatorname{calc}(i,j)$，接下来分类讨论：

• 若下一次选择的日期把两个连续段连了起来：

  • 消去长度为 $3$ 的工作日段的方案数为 $de3=j\times\operatorname{calc}(i+3,j-1)$，有转移

    $\frac{ech}{D-i}\times de3\to dp_{i+3,j-1}$

  • 消去长度为 $2$ 的工作日段的方案数为 $de2=2\times j\times\operatorname{calc}(i+2,j-1)$，有转移

    $\frac{ech}{D-i}\times de2\to dp_{i+2,j-1}$

• 若下一次选择的日期并入了某个连续段：

  • 紧挨着之前的连续段的方案数为 $wi1=2\times j\times \operatorname{calc}(i+1,j)$，有转移

    $\frac{ech}{D-i}\times wi1\to dp_{i+1,j}$

  • 和之前某个连续段之间只间隔一天的方案数为 $wi2=2\times j\times \operatorname{calc}(i+2,j)$，有转移

    $\frac{ech}{D-i}\times wi2\to dp_{i+2,j}$

• 下一次选择的日期单独开一个连续段的方案数即为 $lft=all-de3-de2-wi1-wi2$，有转移

  $\frac{ech}{D-i}\times lft\to dp_{i+1,j+1}$

最后计算答案考虑期望在有 $i$ 天假期时停留多少轮即可，利用等比数列求和公式推导，有：

$\begin{aligned} ans&=\sum\limits_{i=1}^{D-K-1}\sum\limits_{j=1}^{i} dp_{i,j}\times i^t\times\sum\limits_{k=0}^{\infin}\left(\frac{i}{D}\right)^k\\ &=\sum\limits_{i=1}^{D-K-1}\sum\limits_{j=1}^{i} dp_{i,j}\times i^t\times\frac{1}{1-\frac{i}{D}}\\ \end{aligned}$

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=2005;
const int p=998244353;

int D,K,t;
int C[S][S],dp[S][S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int inv(int x)
{
	return qpow(x,p-2);
}

inline int calc(int n,int m)
{
	int val=D-n;
	if(val==0&&m==0) return 1;
	if(val-m<=0||m<=0) return 0;
	return C[val-m-1][m-1];
}

int main()
{
	freopen("holiday.in","r",stdin);
	freopen("holiday.out","w",stdout);
	C[0][0]=1;
	for(int i=1;i<=S-3;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	scanf("%d%d%d",&D,&K,&t);
	dp[1][1]=1;
	for(int i=1;i<=D-K-2;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(dp[i][j]==0) continue;
			int all=1ll*(D-i)*calc(i,j)%p;
			int ech=1ll*dp[i][j]*inv(calc(i,j))%p;
			int de3=1ll*j*calc(i+3,j-1)%p;
			int de2=1ll*2*j*calc(i+2,j-1)%p;
			int wi1=1ll*2*j*calc(i+1,j)%p;
			int wi2=1ll*2*j*calc(i+2,j)%p;
			int lft=(((long long)all-de3-de2-wi1-wi2)%p+p)%p;
			add(dp[i+3][j-1],1ll*ech*inv(D-i)%p*de3%p);
			add(dp[i+2][j-1],1ll*ech*inv(D-i)%p*de2%p);
			add(dp[i+1][j],1ll*ech*inv(D-i)%p*wi1%p);
			add(dp[i+2][j],1ll*ech*inv(D-i)%p*wi2%p);
			add(dp[i+1][j+1],1ll*ech*inv(D-i)%p*lft%p);
		}
	}
	int ans=0;
	for(int i=1;i<=D-K-1;i++)
	{
		int sum=0;
		for(int j=1;j<=i;j++) add(sum,dp[i][j]);
		add(ans,1ll*sum*qpow(i,t)%p*inv((1-1ll*i*inv(D)%p+p)%p)%p);
	}
	printf("%d\n",ans);
	return 0;
}