这篇文章上次修改于 690 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
A:
hs都水讲过了还做不来，建议回去反省上课摸了多久的鱼。
矩阵乘法有结合律所以符合
$A_n==({A_{n/2}})^2(n\equiv 0\mod 2)$
$A_n==A_{n-1}*A(n\equiv 1\mod 2)$
所以直接快速幂，快点写。建议练习用矩阵乘法计算斐波拉契序列。
B:(YTC息怒)
背包问题的典型变形。（只不过是增加了附件可以选择）
考虑到有人没看过01背包问题所以这个题解姑且算个入门吧。
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。
接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2样例输出 #1
3提示
【数据范围】
- 对于 $30\%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。
设计状态$dp_{ij}$为在考虑前i个药后，背包容量为j的情况。
动态转移方程易得：
不选$i$：$dp_{ij}=dp_{(i-1) j}$
选$i$：$dp_{ij}=dp_{(i-1) (j-(t_{i}))}+cost_i$
选最大即可。
枚举顺序外层枚举物品，内层枚举背包容量（从大到小）
为什么从大到小？？？
因为这样可以避开多次选择，因为你会从背包容量小的进行转移，而这些方向暂时未考虑这个物品，所以不会多次选择。
优化（压缩掉i维）：
直接将第一维去掉就好了。
回到这道题其实就是多了转移方式而已。
if(j-a[i]>=0)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
if(j-a[i]-c[i]>=0&&c[i]!=0)
dp[j]=max(dp[j],dp[j-a[i]-c[i]]+b[i]+d[i]);建议去做一下这道题：P1064
可以去机房群找我传的4.zip，里面有背包问题的递推方案。
嘿嘿嘿，应该来看这道题了
其实只是一个变式，递推式变了而已。
考虑三种情况不选，只选主件，和两个都选
建议自己去推递推式。（这里挖了一个坑，如果神奇的错了部分点，可以私聊WXT）。
第三道题：
单调队列水题，不会建议22号找hs挨打。
第四道题：
很容易发现无论怎样操作$A_i$一定是$c$的n次方。所以只用存是$c$的几次方就行了。把一段数乘上$c$,就变成了加上$1$（差分啊）。
取模不要搞错了qwq。