算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   给长度为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 西月弦 阅读(348) 评论(0)  编辑 收藏 引用 所属分类: 解题报告codeforces

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理