「洛谷P5591」小猪佩奇学数学

解锁新姿势。

传送门

洛谷P5591

题解

如果你会NTT或者FFT，那么要理解起来就会比较容易。

首先来看下单位根反演的式子：

$$[k\mid n]=\frac{1}{k}\sum_{i=0}^{k-1}{\omega_{k}^{ni}}$$

证明还是比较简单的，分类讨论一下：

1. 如果$k\mid n$，那么

   $$\frac{1}{k}\sum_{i=0}^{k-1}{\omega_{k}^{ni}}=\frac{1}{k}\sum_{i=0}^{k-1}{(\omega_{k}^{k})^{\frac{n}{k}\cdot i}}=1$$

2. 如果$k\nmid n$，那么

   $$\frac{1}{k}\sum_{i=0}^{k-1}{\omega_{k}^{ni}}=\frac{1}{k}\times\frac{1-(\omega_{k}^{n})^{k}}{1-\omega_{k}^{n}}=\frac{1}{k}\times\frac{1-(\omega_{k}^{k})^{n}}{1-\omega_{k}^{n}}=0$$

本题中模数为$998244353$，原根为$3$，用这个来代就好了。

然后让我们来推题目里的式子：

$$\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times\lfloor\frac{i}{k}\rfloor}\\ =\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times\frac{i-i\mod k}{k}}\\ =\frac{1}{k}(\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times i}-\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times (i\mod k)})\\ =\frac{1}{k}(\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times i}-\sum_{i=0}^{n}{\sum_{d=0}^{k-1}{d\times \tbinom{n}{i}\times p^i\times [i\mod k==d]}})\\$$

先推括号里的前半部分，把乘$i$弄到组合数里，再用二项式定理把式子化为幂的形式：

$$\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times i}\\ =\sum_{i=0}^{n}{\frac{n!}{i!(n-i)!}\times p^i\times i}\\ =n\sum_{i=1}^{n}{\frac{(n-1)!}{(i-1)!(n-i)!}\times p^i}\\ =np\sum_{i=1}^{n}{\tbinom{n-1}{i-1}\times p^{i-1}}\\ =np\sum_{i=0}^{n-1}{\tbinom{n-1}{i}\times p^{i}}\\ =np\times(p+1)^{n-1}$$

再来推后半部分，套上单位根反演的式子：

$$\sum_{i=0}^{n}{\sum_{d=0}^{k-1}{d\times \tbinom{n}{i}\times p^i\times [i\mod k==d]}}\\ =\sum_{i=0}^{n}{\sum_{d=0}^{k-1}{d\times \tbinom{n}{i}\times p^i\times [k\mid i-d]}}\\ =\sum_{i=0}^{n}{\sum_{d=0}^{k-1}{d\times \tbinom{n}{i}\times p^i\times \frac{1}{k}\sum_{j=0}^{k-1}{\omega_{k}^{(i-d)\times j}}}}\\ =\frac{1}{k}\sum_{i=0}^{n}{\sum_{d=0}^{k-1}{d\times \tbinom{n}{i}\times p^i\times\sum_{j=0}^{k-1}{\frac{\omega_{k}^{ij}}{\omega_{k}^{dj}}}}}\\ =\frac{1}{k}\sum_{j=0}^{k-1}{\sum_{d=0}^{k-1}{\frac{d}{\omega_{k}^{dj}}\sum_{i=0}^{n}{\tbinom{n}{i}\times p^i\times(\omega_{k}^{j})^i}}}\\ =\frac{1}{k}\sum_{j=0}^{k-1}{\sum_{d=0}^{k-1}{\frac{d}{\omega_{k}^{dj}}\times(p\times\omega_k^j+1)^n}}\\ =\frac{1}{k}\sum_{j=0}^{k-1}{(p\times\omega_k^j+1)^n\sum_{d=0}^{k-1}{d\times(\omega_k^j)^d}}$$

式子的最后一部分就是一个等差数列乘以等比数列，随便推一下$O(1)$求和的式子就好了，注意分母不能为0要特判。

代码

代码还是挺短的。

#include<cstdio>
using namespace std;
typedef long long LL;
const int TT=998244353;
int n,p,k,ans,gk;
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void Inc(int& x,int y){x=(x+y)%TT;}
inline void Dec(int& x,int y){x=(x-y+TT)%TT;}
inline int S(int r)
{
	if(r==1) return (LL)k*(k-1)/2%TT;
	int inv=QP(r-1,TT-2);
	return ((LL)k*QP(r,k)%TT*inv%TT-(LL)(QP(r,k+1)-r+TT)%TT*inv%TT*inv%TT+TT)%TT;
}
int main()
{
	scanf("%d%d%d",&n,&p,&k);
	gk=QP(3,(TT-1)/k);
	Inc(ans,(LL)n*p%TT*QP(p+1,n-1)%TT);
	for(int j=0;j<k;j++)
	{
		int gkj=QP(gk,j);
		Dec(ans,(LL)QP(k,TT-2)*QP(((LL)p*gkj+1)%TT,n)%TT*S(QP(gkj,TT-2))%TT);
	}
	ans=(LL)ans*QP(k,TT-2)%TT;
	printf("%d\n",ans);
	return 0;
}