T1
是dp 设f i 0 不含k的情况书 f i 1 含k的情况数
第一步优化：前缀和 维护 f两个数组的前缀和 通过前缀转移
第二步优化：发现前缀和能矩阵乘法优化，所以矩阵快速幂就可以
说起来挺简单，式子也不算难推，但就特别难写，主要的难度在于设置矩阵上面
T2
不知怎么一直卡在35，但是打的总体上肯定是没问题的
首先注意审题，这个抽象的边条件，代表的其实是MST，所以暴力15分就来了
然后是 部分分—>正解的部分
考虑对于树的部分，采用类似于边分治的一种方法，然后用树dp维护子树上的情况数，用跨越根节点的情况更新
然后考虑图，我们怎样从图中调整出一个树呢，看条件，我们选择树边之后，一定要保证所有非树边权值大于树边，直接在分治同时维护即可
打了一晚上，还是35，日报写的比较简略
看来课件发不出来了，这就……，看看每天早上能不能提前看出来几道题吧
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。