题解[LuoguP5591]小猪佩奇学数学

前置知识

  1. 基本数论推式子能力,如分配律结合律
  2. 等比数列求和 \(\sum_{i=a}^bx^i=\dfrac{x^{b+1}-x^a}{x-1}\)
  3. 二项式定理 \((a+b)^k=\sum_{i=0}^k\dbinom ki a^ib^{k-i}\) 及其特殊形式 \((a+1)^k=\sum_{i=1}^k\dbinom ki a^i\)
  4. 组合恒等式 \(m\dbinom nm=n\dbinom {n-1}{m-1}\)
  5. 单位根反演 \([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; 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;
}

最新文章

  1. ionic ngCordova插件安装
  2. 为模版设计师而生的Twig(下)-Twig使用指南
  3. C# 常见面试题1
  4. [本人开发的游戏] Discuz网页动物园插件1.0Beta发布!让积分流动起来!
  5. 『.Net』微软家的女儿们
  6. Python之路-python环境安装和简单的语法使用
  7. char型变量理解
  8. Android-兼容问题
  9. linux centos下安装g++
  10. map的infowindow的show事件(ArcGIS API for JS)
  11. 清北学堂Day2
  12. java学习之—链表(2)
  13. pycharm同级目录导入问题
  14. opencv error: insufficient memory错误解决办法
  15. 一篇文章让你读懂iOS和Android的历史起源
  16. (4.25)格式化T-SQL工具
  17. Delphi的子类化控件消息, 消息子类化
  18. php分享二十六:支付系统设计
  19. 深入云存储系统Swift核心组件:Ring实现原理剖析
  20. Java如何比较两个数组是否相等?

热门文章

  1. Quartz 使用教程
  2. 创建a标签使用get请求下载文件
  3. 【Redis场景3】缓存穿透、击穿问题
  4. 1、Spring源码环境搭建
  5. 【LeetCode字符串#03】图解翻转字符串中的单词,以及对于for使用的说明
  6. Vue.config.js配置 最新可用版本
  7. 线程基础知识-CountDownLatch
  8. SpringMVC返回值类型及响应数据类型
  9. 图卷积神经网络分类的pytorch实现
  10. day01-Mybatis介绍与入门