题目描述：
给长度为n的数列，(n<1e5)。让你求选择没有相同的lucky number的子序列的方法数 mod 1e9+7。
算法分析：
首先，小于1e9的lucky number是不超过2^10个的。
那么对于给定长度的len，如何在m个lucky number中选择len个不同的数呢。
这就是一个多重背包的模型。
dp[i][j]代表i个物品，选择j个的方案数。mnt[i]代表第i个物品的数量。
dp[i][j] = dp[i-1][j] (不选i) ＋ (dp[i-1][j-1] *mnt[i])
然后答案就是sum(dp[m][i] * C(cnt,k-i)) ，cnt是非lucky number的数量。
C那一部分就用递推来搞，乘一个数，再乘一个逆元（数论大家都学过）。预处理出来就好了。
代码：
http://codeforces.com/contest/145/submission/2679629
posted on 2012-11-30 18:39
西月弦 阅读(455)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
codeforces