题解 P5591 【小猪佩奇学数学】
Jμdge
2019-10-26 08:04:45
一发 rk4 （如果把前面的两条鱼去重的话应该算是 rk3），感觉没什么好优化的了啊...前面的鱼为啥这么强，日常 ~~摸~~ 膜鱼 【雾
先来讲讲咱一开始的思路：
$$\begin{aligned} Res= {1\over k} \Big(\sum_{i=0}^n \binom{n}{i} \times p^i \times i -\sum_{i=0}^n \binom{n}{i} \times p^i \times (i \% k) \Big) \end{aligned}$$
前半部分很 sb ，等于 $np(p+1)^{n-1}$，后半部分尝试单位根搞
$$\begin{aligned} &\sum_{i=0}^n \binom{n}{i} \times p^i \times (i \% k) \\=& \sum_d d \sum_{i=0}^n \binom{n}{i} \times p^i [k|(i-d)] \\ =& \sum_{d=0}^{k-1} d \sum_{i=0}^n \binom{n}{i} \times p^i \sum_{j=0}^{k-1} \omega_k^{(i-d)j} \\ =& \sum_{d=0}^{k-1} d \sum_{j=0}^{k-1} \omega_k^{-dj} \sum_{i=0}^n \binom{n}{i} \times p^i \omega_k^{ij} \\ =& \sum_{d=0}^{k-1} d \sum_{j=0}^{k-1} \omega_k^{-dj} ( \omega_k^j p +1)^n \\ \end{aligned}$$
然后咱死了，好像不大会搞（虽说大概晓得这玩意儿可以用白兔之舞里面的质数积拆分搞成 法法塔的形式然后同样 k log k 玩...然鹅咱根本就不想打 法法塔 嘤嘤嘤）
于是在 苏指导 的指导下通过了此题...
首先咱发现原来的题目中最为棘手的是那个整除操作：
咱把那玩意儿转化一下，即 $\lfloor {i\over k} \rfloor = \sum_{j=0}^i [k|j] -1$ ，发现其实这玩意儿可以从 1 开始搞 ： $\lfloor {i\over k} \rfloor = \sum_{j=1}^i [k|j] $
然后套单位根反演：
$$\lfloor {i\over k} \rfloor = \sum_{j=1}^i [k|j] = \sum_{j=1}^i \sum_{d=0}^{k-1} \omega_k^{dj} = \sum_{d=0}^{k-1} \omega_k^d {\omega_k^{id}-1\over \omega_k^d -1} $$
后面那玩意儿就是等比数列求和，然后咱带入原式：
$$\begin{aligned}Res&=\sum_{i=0}^{n} \binom{n}{i} p^i \sum_{d=0}^{k-1} \omega_k^d {\omega_k^{id}-1\over \omega_k^d -1} \\ &= \sum_{d=0}^{k-1} {\omega_k^d\over \omega_k^d -1} \sum_{i=0}^{n} \binom{n}{i} p^i ( \omega_k^{id}-1) \\&= \sum_{d=0}^{k-1} {\omega_k^d\over \omega_k^d -1} \Big( \sum_{i=0}^{n} \binom{n}{i} p^i \omega_k^{id} -\sum_{i=0}^{n} \binom{n}{i} p^i \Big) \\&= \sum_{d=0}^{k-1} {\omega_k^d\over \omega_k^d -1} \Big( (\omega_k^dp+1)^n - (p+1)^n\Big) \end{aligned}$$
然后就好 $k log n$ 计算了 【雾 ，假的
注意到 对于 d 不为 0 的其情况，等比数列求和时的 公比 $\omega_k^d$ 是不为 1 的，但是 $d=0$ 时就会出事，所以 d=0 的情况单独讨论：
$$\begin{aligned}Res_0&=\sum_{i=0}^{n} \binom{n}{i} p^i i \\&=\sum_{i=1}^{n} \binom{n}{i} p^i i \\ &= \sum_{i=1}^{n} \binom{n-1}{i-1} p^i n \\&=np\sum_{i=1}^{n} \binom{n-1}{i-1} p^{i-1} \\&=np (p+1)^{n-1} \end{aligned}$$
原来是可以 log n 计算的东西 呢
那么，答案就是：
$$Res=np (p+1)^{n-1} + \sum_{d=0}^{k-1} {\omega_k^d\over \omega_k^d -1} \Big( (\omega_k^dp+1)^n - (p+1)^n\Big) $$
# Code
```
//by Judge (zlw ak ioi)
#include<cstdio>
#include<cstring>
#include<iostream>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
using namespace std;
const int mod=998244353;
int n,p,k,w,wj,pn,res;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void Pls(int& x,int y){if((x+=y)>=mod)x-=mod;}
inline int inc(int x,int y){return (x+=y)>=mod?x-mod:x;}
inline int qpow(int x,int p=mod-2){ Rg int s=1;
for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;
}
int main(){ scanf("%d%d%d",&n,&p,&k),w=qpow(3,(mod-1)/k);
Pls(res,mul(mul(n,p),pn=qpow(p+1,n-1))),pn=mul(pn,p+1),wj=w;
fp(i,1,k-1) Pls(res,mul(mul(wj,qpow(wj-1)),inc(qpow(mul(p,wj)+1,n),mod-pn))),wj=mul(wj,w);
return !printf("%d\n",mul(res,qpow(k)));
}
```