题解[LuoguP5591]小猪佩奇学数学
前置知识
- 基本数论推式子能力，如分配律结合律等
- 等比数列求和 \(\sum_{i=a}^bx^i=\dfrac{x^{b+1}-x^a}{x-1}\)
- 二项式定理 \((a+b)^k=\sum_{i=0}^k\dbinom ki a^ib^{k-i}\) 及其特殊形式 \((a+1)^k=\sum_{i=1}^k\dbinom ki a^i\)
- 组合恒等式 \(m\dbinom nm=n\dbinom {n-1}{m-1}\)
- 单位根反演 \([d\mid n]=\dfrac 1d\sum_{i=0}^{d-1} \omega_d^{ni}\)
题意简述
求
\[\begin{aligned} \sum_{i=0}^n\binom ni p^i \left\lfloor\frac ik\right\rfloor \end{aligned} \]其中 \(n,p,k\) 给定，对 \(998244353\) 取模。
解题过程
可以发现如果去掉最后的 \(\left\lfloor\dfrac ik \right \rfloor\)，那么二项式定理逆用即可，所以我们考虑保留前半部分不动。
要处理 \(\left\lfloor\dfrac ik \right\rfloor\) 类问题，一般依靠其下取整取值数量来做题，但可以发现 \(f(i)=\dbinom ni p^i\) 不方便前缀和，难以使用这个套路。
所以我们考虑转换，将其改写为 \(g(x)=\sum_{i=0}^x[k|i]-1\)，这里为了方便我们将 \(0\) 也算入其中。
那么就可以再使用单位根反演了。
\[\begin{aligned} ans&=\sum_{i=0}^n\binom ni p^i \left\lfloor\frac ik\right\rfloor\\ &=\sum_{i=0}^n\binom ni p^i \sum_{j=0}^i [k|j]-\sum_{i=0}^n\binom ni p^i\\ &=\sum_{i=0}^n\binom ni p^i \sum_{j=0}^i \frac 1k\sum_{l=0}^{k-1}\omega_k^{lj}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\sum_{i=0}^n\binom ni p^i \sum_{j=0}^i\left(\omega_k^l\right)^j-(p+1)^n \end{aligned} \]这时候可以看到出现了 \(\sum_{j=0}^i\left(\omega_k^l\right)^j\)，是一个等比数列求和。
\[\begin{aligned} ans&=\frac 1k \sum_{l=0}^{k-1}\sum_{i=0}^n\binom ni p^i \sum_{j=0}^i\left(\omega_k^l\right)^j-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\sum_{i=0}^n\binom ni p^i \frac{\left(\omega_k^l\right)^{i+1}-1}{\omega_k^l-1}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\frac{\sum_{i=0}^n\binom ni p^i \left(\omega_k^{l(i+1)}-1\right)}{\omega_k^l-1}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\frac{\sum_{i=0}^n\binom ni p^i \omega_k^{l(i+1)}-\sum_{i=0}^n\binom ni p^i}{\omega_k^l-1}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\frac{\sum_{i=0}^n\binom ni p^i \omega_k^{l(i+1)}-(p+1)^n}{\omega_k^l-1}-(p+1)^n\\ \end{aligned} \]这下看上去完全推不动了。。。我们再重新审视一下这一个式子，分析一下现在能做到什么复杂度：显然是 \(O(nk)\) 过不了，考虑得把内层 \(O(n)\) 枚举给省掉，而且其类似于二项式定理的形态也激起了我们化简这一部分的欲望。
所以我们把这一段单独拿出来看一下。
\[\begin{aligned} \sum_{i=0}^n\binom ni p^i \omega_k^{l(i+1)} \end{aligned} \]如果需要逆用二项式定理，需要去掉最后的 \(\omega_k^{l(i+1)}\)。这个幂的表示看起来不太舒服，换成舒服的形式再放回去试一试：
\[\begin{aligned} &\sum_{i=0}^n\binom ni p^i \omega_k^{l(i+1)}\\ &=\sum_{i=0}^n\binom ni p^i \left(\omega_k^l\right)^{i+1}\\ &=\sum_{i=0}^n\binom ni p^i \left(\omega_k^l\right)^i\omega_k^l\\ &=\omega_k^l\sum_{i=0}^n\binom ni p^i \left(\omega_k^l\right)^i \end{aligned} \]这时可以看到我们将 \(p\) 和 \(\omega_k^l\) 的指数都化成了相同的 \(i\)，那我们可以将二者合并起来看，一起放入二项式定理中。
\[\begin{aligned} ans&=\frac 1k \sum_{l=0}^{k-1}\frac{\omega_k^l\sum_{i=0}^n\binom ni p^i \left(\omega_k^l\right)^i-(p+1)^n}{\omega_k^l-1}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\frac{\omega_k^l\sum_{i=0}^n\binom ni \left(p \omega_k^l\right)^i-(p+1)^n}{\omega_k^l-1}-(p+1)^n\\ &=\frac 1k \sum_{l=0}^{k-1}\frac{\omega_k^l \left(p \omega_k^l+1\right)^n-(p+1)^n}{\omega_k^l-1}-(p+1)^n\\ \end{aligned} \]这时，我们就可以用外层 \(O(k)\) 的复杂度枚举，内层 \(O(\log)\) 级别的复杂度计算快速幂，总复杂度 \(O(k\log n)\) 解决这个问题。
另外注意到一点：在使用等比数列求和公式时，我们没有去验证 \(\omega_k^l-1\ne 0\) 的前提条件；而当 \(l=0\) 时，\(\omega_k^l=0\)。
这时我们可以直接特判：
\[\begin{aligned} &\sum_{i=0}^n\binom ni p^i\sum_{j=0}^i\omega_k^0\\ &=\sum_{i=0}^n\binom ni p^i(i+1)\\ &=\sum_{i=1}^ni\binom ni p^i+(p+1)^n\\ &=\sum_{i=1}^n n\binom {n-1}{i-1} p^i+(p+1)^n\\ &=\sum_{i=0}^{n-1} n\binom {n-1}i p^{i+1}+(p+1)^n\\ &=np\sum_{i=0}^{n-1} \binom {n-1}i p^i+(p+1)^n\\ &=np(p+1)^{n-1}+(p+1)^n\\ \end{aligned} \]注：可以看到从有一处开始将 \(\sum\) 的下界改成了 \(i=1\)，这是因为当 \(i=0\) 时无贡献。
最后再把整个式子弄出来：
\[\begin{aligned} ans&=\frac 1k \sum_{l=1}^{k-1}\frac{\omega_k^l \left(p \omega_k^l+1\right)^n-(p+1)^n}{\omega_k^l-1}-(p+1)^n+\frac{np(p+1)^{n-1}+(p+1)^n}k\\ \end{aligned} \]推式子部分结束。
核心代码
只给出核心代码以供参考，不会实现可以看一看，附有简要注释。数论题还挺好实现罢
typedef long long LL;
const int K=1<<20;
const LL MOD=998244353;
inline int read(){
char c=getchar();
int res=0;
bool b=0;
while(c>'9'||c<'0')b=(c=='-'),c=getchar();
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return b?-res:res;
}
LL n,k,p,ik;//ik 是 inv of k
LL omg;//omega
LL ans;
LL Pow(LL x,LL b=MOD-2){
LL res=1;
while(b){
if(b&1)
res=res*x%MOD;
x=x*x%MOD;
b>>=1;
}
return res;
}
LL G(LL x){//计算 mod 998244353 意义下的 x 次单位元
return Pow(3,(MOD-1)/x);
}
int main(){
n=read(),p=read(),ik=Pow(k=read());
omg=G(k);
for(int i=1;i<k;++i){//处理 sigma 内
int ol=Pow(omg,i);
ADD(ans,(ol*Pow((p*ol%MOD+1)%MOD,n)%MOD+MOD-Pow((p+1)%MOD,n))%MOD*Pow(ol+MOD-1)%MOD);
}
ADD(ans,(n*p%MOD*Pow((p+1)%MOD,n-1)%MOD+Pow((p+1)%MOD,n))%MOD);//处理 l=0
ans=ans*ik%MOD;
ADD(ans,MOD-Pow((p+1)%MOD,n));//处理多出来的
printf("%lld\n",ans);
return 0;
}