題目描述：
給長度為n的數(shù)列，(n<1e5)。讓你求選擇沒有相同的lucky number的子序列的方法數(shù) mod 1e9+7。
算法分析：
首先，小于1e9的lucky number是不超過2^10個的。
那么對于給定長度的len，如何在m個lucky number中選擇len個不同的數(shù)呢。
這就是一個多重背包的模型。
dp[i][j]代表i個物品，選擇j個的方案數(shù)。mnt[i]代表第i個物品的數(shù)量。
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的數(shù)量。
C那一部分就用遞推來搞，乘一個數(shù)，再乘一個逆元（數(shù)論大家都學過）。預處理出來就好了。
代碼：
http://codeforces.com/contest/145/submission/2679629
posted on 2012-11-30 18:39
西月弦 閱讀(486)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
codeforces