题意：输入n, m, k, 将n表示成多个数字相加的形式，但是但是不能包含对k取余余数为m的数字。
这个题正解是dp，但是数据量很小，只要姿势对，还是能爆过的，而且时间并不慢，9ms就跑完了，一开始用了记忆化搜索，但是去掉以后时间竟然是一样的。
这题其实一开始看了很久没看懂题意，看懂先随便暴了一下，样例出的就有点慢，然后换了种姿势重新暴，发现运行很快。
n最大30，如果枚举每个数字（也就是我一开始用的方法），会非常慢，有的数据10s都跑不完，但是我们可以换一种枚举方法，枚举每个数字出现了多少次，最后根据排列组合计算能排列成多少种答案，为了避免重复，我们保证先枚举到得数字总是比后枚举到得数字大。
对于有重复数字的排列，用总体排列除以相同数字的内部排列(如果我描述的不清楚可以直接看代码或者问度娘)，但是总体数字可能会超long long，所以对整体排列我直接除以了最小数字的内部排列，这样就可以避免超long long，因为除去最小数字以后数字个数就可以控制在15以内了。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int dp[40][40][40]; int pw[100]; int ans, m, k; int d[100]; ll AAA(int u, int b) { ll ans = 1; for(int i = b + 1; i <= u; i++) ans *= i; return ans; } void dfs(int n, int mx, int u, int s) { if(!n) { ll t = AAA(s, d[u - 1]); for(int i = 0; i < u - 1; i++) t /= AAA(d[i], 0); ans += t; return; } for(int i = min(mx, n); i > 1; i--) { if(i % k == m) continue; for(int j = 1; j * i <= n; j++) { d[u] = j; dfs(n - i * j, i - 1, u + 1, s + j); } } if(1 % k == m) return; d[u] = n; dfs(0, 0, u + 1, s + n); } void init() { pw[0] = 1; for(int i = 1; i <= 30; i ++) pw[i] = pw[i - 1] * 2; memset(dp, -1, sizeof(dp)); } int main() { int t, n, ks; init(); scanf("%d", &t); while(t--) { scanf("%d%d%d%d", &ks, &n, &m, &k); ans = 0; dfs(n, n, 0, 0); // dp[n][m][k] = ans; printf("%d %d\n", ks, ans); } return 0; }
