题目链接 如果边权都是\(1\)，那么矩阵\(i,j\)表示的就是单位时间\(i\)到\(j\)的方案数。 假设\(f-t\)表示在\(t\)时刻的方案数矩阵，\(f-t[i][j]=\sum\limits_{k=1}^{n}=f_{t-1}[i][k]*f_{1}[k][j]\) 显然是可以用矩阵乘法直接算的。 即\(f-t=f_{t-1}*f-1\) 那么现在边权不为\(1\)了，拆点，把

题目链接 设\(f[i][j]\)表示考虑准考证号\(i\)的后缀与 A 长度为\(j\)的前缀匹配的方案数。 \(f[i][j]=\sum\limits_{k=0}^{n}f[i-1][k]\times g[k][j]\) \(g[k][j]\)表示填入有多少个数字使匹配长度从\(k\)变成\(j\) 第二个可以用 kmp 预处理。 dp 方程是矩乘的形式，可以用矩阵乘法优化。 123456

普通版题目链接 k=1 所有数异或起来，最后的异或和就是答案 k=2 如果和上一样的做法，最后会得到两个数异或的结果。 既然是两个不同数，那么二进制下也一定有一位不一样。 我们开按位置来异或，\(a[i]\)表示第\(i\)位为\(1\)的数的异或和，\(b[i]\)表示第\(i\)位为\(0\)的数的异或和。 因为同一个数一定会在一个桶里面异或，那么出现偶数次的是没有影响的。 最后只有两个出

提供一种题解没有提到的做法。 感觉比题解的 dp 自然？ 因为要求某两种n顔色出现偶数次，那我们直接枚举好了。 \(\sum\limits_{i=0}^n\sum\limits_{j=0}^{n-i}\binom{n}{i}\binom{n-i}{j}[2\mid i][2\mid j]2^{n-i-j}\) 很自然能够想到\[\sum\limits_{i=0}^{n}\binom{n}{i}[2

OI

题目链接 因为是没有负环的，所以可以用 spfa 好像有点卡？ 用双端队列过了，听说双端队列优化是假的？ 啊，这... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <bits/stdc++.h>using n

题目链接 之前听学长讲过，好像是在 dp 专题讲的？ 这东西好像不是很 dp 啊。 先想想暴力的做法。 问题一直接枚举起点后模拟一下，\(\mathjaxcal{O}(n^3)\) 问题二一样的模拟... 有两个优化，可以先预处理一下每个点对应的最小和次小的目的地，之后直接走。 二是每次决策好像都差不多，可不可以一次多走几步... 第一个，因为只能往东走，所以西边的点对东方没有影响。 可以在一

题目链接 二维前缀和直接枚举顶点统计答案。 可不可以不枚举呢？ 如果两个前缀和在模\(k\)意义下相等，那这两个前缀和的子矩阵是\(k\)的倍数。 所以问题变成统计所有和相等的子矩阵对数。 可以枚举上下边，就可以统计所有以此为上下边的矩阵合法的对数。 注意要求的是单个矩阵是\(k\)的倍数，所以两个前缀和相减要是有意义的。 12345678910111213141516171819202122

题目链接 感觉自己代码能力好弱啊.... 约数个数和定理 枚举每个约数的指数，然后 dfs 一下。 特判指数为 1 的情况， 如果某个未用过的素数满足\(sum\times (p-i+1)=S\),就记录一下答案。 1if (lst > P[x] && isprime(lst - 1)) v[++tot] = (lst - 1) * cur; 还需要枚举所有\(e-i\l

题目链接 把不能在一起的骑士连一条边，可以发现每个连通块最多一个环。 每个联通块单独考虑，变成了选儿子不能选父亲这种经典 dp 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <bits/stdc++.