问题可以转化成，对于二进制的每一位，每位最多用k次，那么能加出n的情况数，
这样其实就一个背包问题，利用记忆化搜索，，减少需要的状态数
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MOD = 1000000009;int w[20];int t, n, k;int dp[20][10005];int solve(int u, int sum) {if (u > 17) return 0;if (dp[u][sum] != -1) return dp[u][sum];dp[u][sum] = 0;if (sum == 0) return dp[u][sum] = 1;int s = sum;for (int i = 0; i <= k; i++) {dp[u][sum] = (dp[u][sum] + solve(u + 1, s)) % MOD;s -= w[u];if (s < 0) break;}return dp[u][sum];}int main() {w[0] = 1;for (int i = 1; i < 20; i++) w[i] = w[i – 1] * 2;scanf("%d", &t);while (t–) {scanf("%d%d", &k, &n);memset(dp, -1, sizeof(dp));printf("%d\n", solve(0, n));}return 0;}
你在无垠的海边第一次听到了自己心跳的声音，
