洛谷P5591 小猪佩奇学数学【单位根反演】

Description

请去传送门阅读。

Solution

柿子中最辣手的无疑是(lfloor dfrac ik floor)了,如果没有它原式就是一个二项式定理,但我们可以将它转化为:

[lfloor frac ik floor=sum_{j=1}^{i}[k|j] ]

然后就可以上单位根反演了,同时我们隐隐猜出了原题的解法是二项式定理,为了凑出二项式定理的柿子,我们将下标改为从(0)开始,

[lfloor frac ik floor=sum_{j=0}^{i}[k|j]-1 ]

代入原式:

[ans=sum_{i=0}^{n}inom ni p^i (sum_{j=0}^{i}frac 1k sum_{d=0}^{k-1}w_k^{dj}-1) ]

提出(-1)并交换和式得:

[egin{aligned} &=frac{1}{k}sum_{d=0}^{k-1}sum_{i=0}^{n}inom ni p^isum_{j=0}^{i}w_k^{dj}- sum_{i=0}^{n}inom ni p^i\ &=frac{1}{k}sum_{d=0}^{k-1}sum_{i=0}^{n}inom ni p^ifrac{w_k^{d(i+1)}-1}{w_k^d-1}- (p+1)^n\ end{aligned} ]

将减号前面的柿子拆成两部分,都是二项式定理的柿子:

[egin{aligned} =frac{1}{k}sum_{d=0}^{k-1}(sum_{i=0}^{n}inom ni p^ifrac{w_k^{d(i+1)}}{w_k^d-1}-sum_{i=0}^{n}inom ni p^ifrac 1{w_k^d-1})- (p+1)^n\ =frac{1}{k}sum_{d=0}^{k-1}(w_k^dfrac{(pw_k^d+1)^n}{w_k^d-1}-frac{(p+1)^n}{w_k^d-1})- (p+1)^n end{aligned} ]

这时候就可以直接做了,注意特判(d=0)时分母为(0)的情况:

此时答案为

[sum_{i=0}^{n}inom{n}{i}p^isum_{j=0}^{i}w_k^0\ =sum_{i=0}^{n}inom{n}{i}p^i(i+1)\ =sum_{i=0}^{n}inom{n}{i}p^ii+sum_{i=0}^{n}inom{n}{i}p^i ]

后一部分不用说,是((p+1)^n),对于前一部分,注意到(dbinom nii=ndbinom {n-1}{i-1}),因此

[=nsum_{i=0}^{n}inom{n-1}{i-1} p^i\ =npsum_{i=0}^{n-1}inom{n}{i}p^i=np(p+1)^{n-1} ]

于是就做完了,复杂度(mathcal O(klog(n)))

Code

比我的题解还短。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline int ksm(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
	return ret; 
}
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
int n,p,k;
int main(){
	scanf("%d%d%d",&n,&p,&k);
	int ret=0,w=ksm(3,(mod-1)/k);
	int np=add(p,1);
	for(int i=0;i<k;++i){
		if(!i) ret=add(ret,add(ksm(np,n),1ll*n*p%mod*ksm(np,n-1)%mod));
		else{
			int ww=ksm(w,i);
			int ans=ksm(dec(ww,1),mod-2);
			ans=1ll*ans*dec(1ll*ww*ksm(add(1ll*p*ww%mod,1),n)%mod,ksm(np,n))%mod;	
			ret=add(ret,ans);
		}
	}
	printf("%d
",dec(1ll*ret*ksm(k,mod-2)%mod,ksm(np,n)));
	return 0;
}
原文地址:https://www.cnblogs.com/tqxboomzero/p/14613612.html