Our happy ending _Happy

枕上诗书闲处好，门前风景雨来佳。这篇文章主要讲述Our happy ending相关的知识，希望能为你提供帮助。
题目链接

题意：
输入n、k、L，n个数，最大值不超过L，在序列中取若干个数和能达到k的序列个数
n,k< =20 , 0< =L< =10^9
分析：
题目关键在于和k比較小，所以能够考虑DP。
先说一下自己比赛时候想到的DP状态。好久才发现错了。
。。。
DP[i][j]表示当前是序列中的第i个数（必须选），和能取到j的序列个数。
这个状态的问题就是在于反复：对于一个确定的序列来说，由于能够选取某些数字来求和，所以对于DP[i]来说，同一个序列能够得到非常多不同的和j，也就是被计算了非常多次从而导致反复。
对照一下之前见过的一个类似的问题，给定一个序列。问取若干个数能达到和k的方案数：DP[i][j]表示当前是序列中的第i个数（必须选），和能取到j的序列个数，这个问题这样表示就是正确的了。
为什么会这样呢？就是由于答案的推断方式不同：第一个问题的答案推断是，当前序列假设能取到若干个数使得和为k。那么答案加一；第二个问题则是，假设有x种方案。从当前序列中取出若干个数使得和为k。那么答案加x。也就是说。第一个问题的推断根据是序列是否满足，第二个则是取出来的集合是否满足。而上述DP的方案事实上就是在选择集合中的元素，由于DP[i][j]表示i必须选，也就是在集合中存在。

那么到此，怎样推断一个序列是否是满足的呢：从左到右枚举序列当前位置的值，那么要求当前序列是否是满足的也就是求和能否到k，那么不可缺少的须要记录一下当前序列所能到达的和都有谁。至此。就能够用状压DP来解了。叙述一下二进制代表的意义：第一个1代表和为1。第二个1表示和为2……
反思一下程序写的时候的问题：没实用滚动数组，导致错了非常多次。
因为这个题目的状态转移仅仅会向更大的状态值（也能够是自己）转移。所以能够不採用滚动数组，一维解决。
可是这样就须要额外注意一个问题。自己转移到自己的问题。因为这里理解的不是非常好。导致一直查不出来BUG。学习了。

const int MAXN = 21; int dp[1 < < MAXN]; int main() { int T, n, sum, Max; RI(T); FE(kase, 1, T) { RIII(n, sum, Max); int Min = min(sum, Max); int all = 1 < < sum; CLR(dp, 0); dp[0] = 1; REP(i, n) { FED(j, all - 1, 0) { if (dp[j] == 0) continue; int x = dp[j]; for (int k = 1; k < = Min; k++) { int nxt = j | ((j < < k) & (all - 1)) | (1 < < (k - 1)); dp[nxt] += x; if (dp[nxt] > = MOD) dp[nxt] -= MOD; } if (Max - Min > 0) dp[j] = (dp[j] + 1LL * (Max - Min) * x) % MOD; } } int ans = 0; FF(i, 1 < < (sum - 1), all) { ans += dp[i]; if (ans > = MOD) ans -= MOD; } WI(ans); } return 0; }

用dp[1]表示0的方法，事实上不好。由于3（11）和2（10）表示的意义是一样的，并且不含或者包括零（第一个一）没有什么意义

const int MAXN = 21; int dp[1 < < MAXN]; int main() { int T, n, sum, Max; RI(T); FE(kase, 1, T) { RIII(n, sum, Max); int Min = min(sum, Max); int all = 1 < < (sum + 1); CLR(dp, 0); dp[1] = 1; REP(i, n) { FED(j, all - 1, 1) { if (dp[j] == 0) continue; int x = dp[j]; for (int k = 1; k < = Min; k++) { int nxt = j | ((j < < k) & (all - 1)); dp[nxt] += x; if (dp[nxt] > = MOD) dp[nxt] -= MOD; } if (Max - Min > 0) dp[j] = (dp[j] + 1LL * (Max - Min) * x) % MOD; } } int ans = 0; FF(i, 1 < < sum, all) { ans += dp[i]; if (ans > = MOD) ans -= MOD; } WI(ans); } return 0; }

【Our happy ending】