矩阵加速递推 n的范围比较小，k的范围很大，我们可以考虑从n入手。 1.首先我们知道任何矩阵*单位矩阵都不会改变. 所以对于交换操作，我们可以造出一个这样的矩阵： 除了第s、m行，其他每一行都是f[i][i]=1; 第s行:f[s][m]=1;第m行:f[m][s]=1; 这样我们就完成了交换操作。 2.对于左移操作，我们也可以造出一个这样的矩阵： 除了第n行，其他每一行都是f[i][i+1]=1; 第n行:f[n][1]=1; 3.我们的初始矩阵f[i][1]=a[i]; 因为矩阵符合结合律，所以我们可以用类似快速幂的方法加速。 然后就可以啦，时间复杂度O(\(n^3...

数位DP|记忆化搜索 听隔壁巨佬说DP和记搜可以互相转换 显然这个题是可以用记忆化搜索过的，那我们应传哪几个参数？ 首先就是记搜最基本的位置标记。 然后就是枚举的数字各位之和，以及取模之后的余数（判断能否整除某个数）。 最后就是判边界的参数。 当我们搜到最后一位时如果余数为0，并且各位之和=mod，那就直接返回1，否则返回零。 显然我们把这几个数装进数组里，是开不下的。 long long 为8字节 \(8\times 20\times 200\times 200\times 200 \div1024 \div1024 =1220.703125 MB8×20×200×200×2...

数位DP|记忆化搜索 听隔壁巨佬说DP和记搜可以互相转换 显然这个题是可以用记忆化搜索过的，那我们应传哪几个参数？ 首先就是记搜最基本的位置标记。 然后就是枚举的数字各位之和，以及取模之后的余数（判断能否整除某个数）。 最后就是判边界的参数。 当我们搜到最后一位时如果余数为0，并且各位之和=mod，那就直接返回1，否则返回零。 显然我们把这几个数装进数组里，是开不下的。 long long 为8字节 \(8\times 20\times 200\times 200\times 200 \div1024 \div1024 =1220.703125 MB8×20×200×200×2...

状压bfs 一共有16个位置，最多会有 \(2^{16}=65536\) 种情况，用数组完全开的下。 用二进制中的1表示该位置有玩具，0表示该位置没有玩具。 由于广搜最先搜到的是最优解，直接用数组记录是否到达过该状态，顺便记录ans. 移动前的状态ans为0. 然后大力讨论12种情况即可 时间复杂度O( \(2^{16}\) )O(能过) 献上我又臭又长的代码 #include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std...

状压bfs 一共有16个位置，最多会有 \(2^{16}=65536\) 种情况，用数组完全开的下。 用二进制中的1表示该位置有玩具，0表示该位置没有玩具。 由于广搜最先搜到的是最优解，直接用数组记录是否到达过该状态，顺便记录ans. 移动前的状态ans为0. 然后大力讨论12种情况即可 时间复杂度O( \(2^{16}\) )O(能过) 献上我又臭又长的代码 #include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std...