【SDOI2017】套路总结
2024-08-30 08:15:36
1
第一题是裸的反演;
\[\begin{align}
Ans&=\prod_{i=1}^n\prod_{j=1}^ma[(i,j)]\\
&=\prod_{d=1}^na[d]^{f(d)}\\
f(d)&=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor\mu(i)
\end{align}\]
考虑更换为枚举\(i*d\),
那么就有,
\[\begin{align}
Ans&=\prod_{k=1}^n\sum_{d|k}a[d]^{\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\mu(\frac{k}{d})}\\
&=\prod_{k=1}^n(\sum_{d|k}a[d]^{\mu(\frac{k}{d})})^{\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor}
\end{align}\]
显然,我们可以预处理\((\sum_{d|k}a[d]^{\mu(\frac{k}{d})})\),于是就能分块做了。
2
如果一个结点与其父亲颜色不同,就给他打上标记1。
3
至少存在一个=存在=所有-不存在;
我们用dp来进行序列计数,\(f[i][j]\)表示前i个数的前缀和%p的值为j的方案数。
显然可以矩阵乘法。
最新文章
- maven如何配置
- 线上应用bug跟踪查找-友盟统计
- PostgreSQL ROW_NUMBER() OVER()
- The Rotation Game(IDA*算法)
- [C语言]一个很实用的服务端和客户端进行UDP通信的实例
- 图表Echarts的使用
- 高效查看MySQL帮助文档的方法
- mysql 中的bool值
- Design Mode 之 行为模式
- Mongoose:Schema之路
- MYSQL数据库备份与恢复【转】
- Effective C++ 第二版 40)分层 41)继承和模板 42)私有继承
- poj1651(区间dp)
- ios animation暂停pause、恢复resume
- 记录近期小改K-Means至MapReduce上的心得
- 异常-----spring明明注入了Service到Action中,为什么运行的时候Service为空,在抽象类中,有子类来继承的
- 《Python神经网络编程》中文版PDF+英文版PDF+源代码,业界良心书
- stark组件之分页【模仿Django的admin】
- HDU 2242 考研路茫茫——空调教室(边双连通分量+树形dp+重边标号)
- Linux改变用户shell的类型