P5591 小猪佩奇学数学

为了方便，所有的分数默认下取整

$$\sum_{i=0}^{n}\binom{n}{i}p^i\times \frac{i}{k}$$

$$n,p\leq [0,998244353)\quad k=2^t(t\in[0,20])$$

$$=\sum_{i=0}^{n}\binom{n}{i}p^i\times \frac{i-i\bmod k}{k}$$

$$=\frac{1}{k}\sum_{i=0}^{n}\binom{n}{i}p^i\times (i-i\bmod k)$$

省略$\dfrac{1}{k}$

$$=\sum_{i=0}^{n}\binom{n}{i}i\times p^i-\sum_{i=0}^{n}\binom{n}{i}p^i\times i\bmod k$$

先看前面一坨，显然看到组合数并且上界很大，肯定是往二项式定理靠

由$\displaystyle \binom{n}{i}=\frac{n}{i}\binom{n-1}{i-1}$

$$=n\sum_{i=0}^{n}\binom{n-1}{i-1}\times p^i$$

$$=np\times (p+1)^{n-1}$$

所以只用看后面那一坨了：

$$\sum_{i=0}^{n}\binom{n}{i}p^i\times(i\bmod k)$$

$$=\sum_{i=0}^{n}\binom{n}{i}p^i\times\sum_{j=0}^{k-1}j[i\equiv j\pmod k]$$

$$=\sum_{i=0}^{n}\binom{n}{i}p^i\times\sum_{j=0}^{k-1}j\times \frac{1}{k}\sum_{t=0}^{k-1}w_{k}^{(i-j)t}$$

$$=\frac{1}{k}\sum_{t=0}^{k-1}(\sum_{i=0}^{n}\binom{n}{i}p^iw_k^{it}\times \sum_{j=0}^{k-1}j\times w_k^{-jt})$$

$$=\frac{1}{k}\sum_{t=0}^{k-1}((pw_k^t+1)^n\times \sum_{j=0}^{k-1}j\times w_k^{-jt})$$

就剩下最后那一点点了：小学生都能解决的**等差乘以等比**

设$\displaystyle x=w_k^{-t}\quad S(L,x)=\sum_{i=0}^{L}i\times x^i$

快速幂算一下就好了

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N=(1<<20)+1;
const int mod=998244353,g=3;
int w[N];
inline int power(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1) res=1ll*res*a%mod;
	return res;
}
inline int S(int L,int x)
{
	if(L==0||x==0) return 0;
	if(x==1) return 1ll*(L+1)*L/2%mod;
	int inv=power(x-1,mod-2),fp=power(x,L+1),res;
	res=(1ll*L*fp%mod-1ll*(fp-x)*inv%mod)%mod;
	return (1ll*res*inv%mod+mod)%mod;
}
int main()
{
	int n,p,k,buf,ans=0;
	scanf("%d%d%d",&n,&p,&k);
	buf=power(g,(mod-1)/k);
	w[0]=1; for(int i=1;i<k;i++) w[i]=1ll*w[i-1]*buf%mod;
	for(int i=0;i<k;i++)
		ans=(ans+1ll*power(1ll*p*w[i]%mod+1,n)*S(k-1,w[(k-i)%k])%mod)%mod;
	ans=1ll*ans*power(k,mod-2)%mod;
	ans=(1ll*n*p%mod*power(p+1,n-1)%mod-ans+mod)%mod;
	printf("%d\n",1ll*ans*power(k,mod-2)%mod);
	return 0;
}
```

正在渲染内容...