5343

这题我们很容易想出一个状态，设f[i][j]表示前i个长度划分长度为j的块的总方案 然后我们自信的写出\(f[i][j]=f[i-1][j]+f[i][j-a[i]]\) 但这其实是错的！这跟背包很想，+f[i][j-a[i]]这一项的本质是说这个长度为j的块的最后一段的长度是a[i]，但其实最后一 ......

f[i ] += f[i-j] j<=100 构造的矩阵: 这种求和的柿子可以化为矩阵乘法，做法是 矩阵对应元素设置0/1 #include <iostream> #include <cstring> #include <map> using namespace std; const int N = ......

https://www.luogu.com.cn/problem/P5343 给定可以取的块长集合，求长度为 $n$ 的块可以有几种分块的方案 考虑 dp，类似于背包计数 $$ f_0 = 1, f_i = \sum_{j} f_{i - a_j} $$ 发现 $n$ 很大，但是 $a_i$ 值域上 ......