本题首先有一个比较容易得到的DP算法
状态：f[i][j]表示最后一位数字是j的i位数中，合法的数有多少个
转移： f[i][j] = ∑f[i-1][t] | t = 0, 1, 2, ... 9 且满足 t * j <= k 且 t <= k
时间复杂度大约是O(n*100)，会超时。
优化的方法是使用矩阵乘法优化DP。
首先我们根据k可以计算出一个10x10的矩阵A[0..9][0..9]:
Aij = [i <= k && j <= k && i * j <= k] ([x]代表：如果x为真，[x] = 1；否则[x] = 0)
然后计算T = A^(N-1)，注意这里可以用快速幂计算矩阵乘法。
最后计算矩阵T的所有元素之和即是答案。
时间复杂度(logn*1000)
解析: 把式子转换一下 a1x1+a3x3+a5x5=a2x2+a4x4+a6x6
先预处理左边的，枚举左边的，用map记录答案出现的次数 再枚举右边，累加答案出现的次数
using namespace std; int k,a1,a2,a3,a4,a5,a6; map v; int main() { cin>>k>>a1>>a2>>a3>>a4>>a5>>a6; for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) for(int m=1;m<=k;m++) { int ans=a1*i+a3*j+a5*m; v[ans]++; } int sum=0; for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) for(int m=1;m<=k;m++) { int ans=a2*i+a4*j+a6*m; sum+=v[ans]; } cout<
