闲话
NFLS。
话说 AT 计数 dp 好题挺多啊。
[ABC248F] Keep Connect
题解区已经讲得十分清楚了。套路地搞 dp，将连通载入其中。\(dp_{i,j，0/1}\) 表示前 \(i\) 列，断了 \(j\) 条边，上下是否连通的方案数。这里我们保证所有的点都与第 \(i\) 列其中的 \(1\) 或两个点相连。然后就可以转移了。这里连通是关键信息，顺序转移是统计。
[ARC166C] LU / RD Marking
思考边与边所产生的冲突。模拟可以发现，只有每条在斜方向延伸的多条曲折的边内部才会有冲突。那么大致方向就是算出每个再相乘。考虑怎么计算，由于每条斜的没有本质区别，只是规模上的扩展。考虑由 \(len\) 条边组成，那么由增量法：选最后一条边，那么倒数第二条必选，规模变为 \(len-2\)；不选，规模变为 \(len-1\)。\(f_i \gets f_{i-1} + f{i_2}\)。斐波那契数列。
[ABC207E] Mod i
这是一个很简单的 dp。\(f_{i,j}\) 表示前 \(i\) 个分为 \(j\) 段的方案数。\(f_{i,j} = \sum [pre_i \equiv pre_k \pmod j ]f_{k,j-1}\)。对于同余这一特性进行优化。辅助数组 \(g_{k}\) 记录 \(sum_x\) 模 \(j\) 余 \(k\) 的 \(f_{k,j-1}\)。将 \(j\) 作为阶段转移即可。
f[0][0] = 1;
for(int j = 1;j<=n;++j){
memset(g,0,sizeof g);
for(int i = 1;i<=n;++i){
toadd(g[a[i-1]%j],f[i-1][j-1]);
toadd(f[i][j],g[a[i]%j]);
}
}
for(int j = 1;j<=n;++j)ans = (0ll + ans + f[n][j])%mod;