P5591 小猪佩奇学数学

15 Feb 2021 2480字 9分次数学
如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）

我们有单位根反演：

[k\mid j]=\frac{1}{k}\sum\limits_{d=0}^{k-1}\omega_{k}^{dj}

证明：

当 $k\mid j$ 时， $\omega_k^j=1$ ，右式 $=1$ 。

当 $k\nmid j$ 时， $\omega_k^j\neq 1$ ，右式 $=\frac{\omega_k^{kj}-\omega_k^{0j}}{\omega_k^j-1}=0$ 。

根据单位根反演：

\begin{aligned} &\sum\limits_{i=0}^n{n\choose i}p^i\left\lfloor\frac{i}{k}\right\rfloor\\ =&\sum\limits_{i=0}^n{n\choose i}p^i(\sum\limits_{j=0}^i[k\mid j]-1)\\ =&\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i[k\mid j]-\sum\limits_{i=0}^n{n\choose i}p^i\\ =&\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\frac{1}{k}\sum\limits_{d=0}^{k-1}\omega_{k}^{dj}-(p+1)^n\\ =&\frac{1}{k}\sum\limits_{d=0}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}-(p+1)^n\\ =&\frac{1}{k}\sum\limits_{i=0}^n{n\choose i}p^i(i+1)+\frac{1}{k}\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}-(p+1)^n\\ \end{aligned}

先算左边的东西：

\begin{aligned} &\sum\limits_{i=0}^n{n\choose i}p^i(i+1)\\ =&\sum\limits_{i=0}^n{n\choose i}p^ii+\sum\limits_{i=0}^n{n\choose i}p^i\\ =&\sum\limits_{i=0}^n{n-1\choose i-1}p^in+(p+1)^n\\ =&np\sum\limits_{i=0}^{n-1}{n-1\choose i}p^i+(p+1)^n\\ =&np(p+1)^{n-1}+(p+1)^n \end{aligned}

然后是中间的东西：

\begin{aligned} &\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\sum\limits_{j=0}^i\omega_{k}^{dj}\\ =&\sum\limits_{d=1}^{k-1}\sum\limits_{i=0}^n{n\choose i}p^i\frac{\omega_{k}^{d(i+1)}-1}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\sum\limits_{i=0}^n{n\choose i}p^i\omega_{k}^{d(i+1)}-\sum\limits_{i=0}^n{n\choose i}p^i}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}\sum\limits_{i=0}^n{n\choose i}(p\omega_{k}^{d})^i-(p+1)^n}{\omega_{k}^{d}-1}\\ =&\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}(p\omega_{k}^{d}+1)^n-(p+1)^n}{\omega_{k}^{d}-1}\\ \end{aligned}

所以原式等于：

\frac{1}{k}\left(np(p+1)^{n-1}+(p+1)^n+\sum\limits_{d=1}^{k-1}\frac{\omega_{k}^{d}(p\omega_{k}^{d}+1)^n-(p+1)^n}{\omega_{k}^{d}-1}\right)-(p+1)^n

时间复杂度 $\mathrm O(k\log n)$ ，复杂度瓶颈是快速幂。

#include<cstdio>
int const mod=998244353;
int o,n,p,k,ans;
int pow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return res;
}
int main(){
	scanf("%d%d%d",&n,&p,&k);
	o=pow(3,(mod-1)/k);
	for(int d=1,i=1;i<k;i++){
		d=1ll*d*o%mod;
		ans=(ans+(1ll*d*pow(1ll*p*d%mod+1,n)-pow(p+1,n)+mod)%mod*pow(d-1,mod-2))%mod;
	}
	ans=(ans+1ll*n*p%mod*pow(p+1,n-1)+pow(p+1,n))%mod*pow(k,mod-2)%mod;
	ans=(ans-pow(p+1,n)+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

P5591 小猪佩奇学数学 gxy001