ER-18
2024-09-25 16:03:18
ER #18简要题解
就是推出循环矩阵乘积
然后一次操作后得到的c矩阵第一行第i列就是i的情况(b矩阵下标是a矩阵下标的转置)
两个循环矩阵乘积还是循环矩阵
以此推式子,发现c矩阵的第一行可以用a,b的第一行用循环卷积的形式表示
循环卷积也有结合律,可以快速幂
得到的多项式就是最终c矩阵第一行,直接输出即可。
emmm。。。
其实不用循环矩阵(这样只是说得方便严谨)
把b多项式reverse
画图可以得到
c=a*b *是循环卷积。
红色插入补充一点:
对于每个ai,质因数分解,枚举出约数。
开2e7个vector记录每个数是哪些数的约数,然后枚举每个数作为约数,遍历vector进行dfs
总复杂度是约数个数的5e7左右
但是2e7个vector会爆炸
开大数组然后分配内存:
cnt[2e7]表示是i的倍数的点多少个。i|d,cnt[i]++
通过cnt大小分配位置
再进行一次,把每个数填进去(这里可以开1e5个vector存约数,就不用再分解了)
第一步这个反演类似莫比乌斯反演
不同的是这是枚举倍数
分析法可以证明(把结果的g用条件换掉,然后大力反演,最后用f*[n==1]得到f)
最新文章
- myeclipse给项目改了名字,但部署tomcat的项目名还是原来的
- [I2C]I2C总线协议图解
- CSS3定位和浮动详解
- 用多itemtype的具有addHeaderView的recyclerview,还是scrollview?
- 一个构建XML对象的js库
- POJ 2960 博弈论
- 鼠标按键自定义软件-X-Mouse Button Control
- SSH架构简单总结
- Python几个算法实现
- socket编程里的read和recv函数【转载】
- Linux进程和线程的比較
- NOIP2014提高组第二题联合权值
- 大神博客链接系列---C#SubSonic3.0搭建ORM
- JS阻止事件冒泡的3种方法之间的不同
- BZOJ1997 平面图判定 平面图性质 2-sat
- 2017-2018-2 20165237 实验二《Java面向对象程序设计》实验报告
- PID控制器开发笔记之十:步进式PID控制器的实现
- leetcode347
- [HTML]html读取本地文件并显示
- mysql主从复制搭建中几种log和pos详解