【DP】组合数字

时间:2022-02-12 20:18:47

Password Attacker

题意就是给 M 个关键字,组合成 N 字符长度的结果,每一个关键字都必须在 N 位的字符中出现,有多少种可能结果。

范围 1 ≤ M ≤ N ≤ 100.

举例假设 M = 3(key = 3, 7, 5)  N = 4 位字符长度

结果可以为3577, 3557, 7353, 5735.

下面的结果是不合法的

1357 // 1 没有在key中,不是合法关键字

3355 // 7 是关键字,但是结果中没有出现

357 // 结果必须是一个4位长度

思路1:

设立状态dp(i, j)表示在 M 个关键字中取前 i 个不同关键字,组成长度为 j . 所有结果总和

划分子问题

1. i == j 时候, 取前 i 个Key组成长度为 i ,结果为 【DP】组合数字

2. i < j 时候,考虑dp(i-1, k),选去第 i 个元素j-k次,第i个元素与前i-1个元素不同,把这j-k个第i个元素插入到已有长度k的序列中,就可以转移到dp(i, j)

3. i > j, 不考虑

那么对于2,如何插入?

已有的 k 个元素有 k+1 个位置可以进行插入,问题就是把 j-k 个元素插入到 k+1 个桶中有多少种结果?

【DP】组合数字 表示第 i 个桶,那么问题就等价于【DP】组合数字的所有非负整数解。

我们把两边同时加上k+1,变成【DP】组合数字 的所有正整数解。

相当于给j+1个1,插入隔板把它们分到k+1个桶中,每个桶要保证至少有一个元素,所以一共有 j 个可以提供插入隔板的位置,总共有k+1个桶,所以需要在这 j 个空隙中选择出k个位置插入隔板就成k+1个桶。

答案为【DP】组合数字

最后的2,也就等于  【DP】组合数字

最后的答案就是dp(m, n)

源码如下:

#include <bits/stdc++.h>
using namespace std; typedef long long int64; const int64 M = 1000000007LL;
const int maxn = 105;
int64 C[maxn][maxn];
int64 dp[maxn][maxn]; void getCombination() {
int n = maxn;
for (int i = 1; i <= n; i++)
C[i][0] = C[i][i] = 1LL; for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
C[i][j] = (C[i-1][j-1] % M + C[i-1][j] % M) % M;
} int main() { getCombination();
int t, m, n, cas = 1;
scanf("%d", &t);
while ( t-- ) {
scanf("%d%d", &m, &n);
// init
memset(dp, 0LL, sizeof(dp));
for (int i = 1; i <= n; i++) dp[1][i] = 1;
for (int i = 2; i <= n; i++) dp[i][i] = (dp[i-1][i-1] * (int64)i) % M; for (int i = 2; i <= m; i++)
for (int j = i+1; j <= n; j++)
for (int k = i-1; k <= j-1; k++)
dp[i][j] = (dp[i][j] + (C[j][k] * dp[i-1][k]) % M) % M; printf("Case #%d: %lld\n", cas++, dp[m][n]);
}
return 0;
}

思路2:

qqz大神,dp(i, j)表示从 M 个元素中随机选取 i 个不同的元素组成 j 的长度的所有结果

划分子问题

1. i == j, dp(i, i) 随机从 M 个元素选取 i 个元素的全排列,为【DP】组合数字

2. i == 1, dp(1, j) 表示从 M 个元素中随机选取一个重复 j 次,结果为 M

3. i < j , 【DP】组合数字,

和的第一部分表示在dp(i-1, j-1)基础上,从剩下的M-i+1个数中取1个放到最后组成dp(i, j). 和的第二部分表示从已经选出的i个元素中挑1个放到最后。

最后的答案就是dp(m, n)

源码如下:

#include <bits/stdc++.h>
using namespace std; using int64 = long long;
const int64 M = 1000000007LL; int64 dp[105][105], A[105][105]; void initA() { for (int i = 1; i <= 100; i++) {
A[i][0] = 1;
for (int j = 1; j <= i; j++)
A[i][j] = ((i-j+1) * A[i][j-1]) % M;
}
} int m, n; int64 f(int i, int j) {
if (dp[i][j] != -1) return dp[i][j];
if (i == j) return dp[i][j] = A[m][i];
else return dp[i][j] = (((m-i+1) * f(i-1, j-1)) % M + (i * f(i, j-1)) % M ) % M;
} int main() {
freopen("A-large-practice.in", "r", stdin);
freopen("a_out.txt", "w", stdout);
int t, cas = 1;
initA();
scanf("%d", &t);
while (t--) {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = -1;
for (int i = 1; i <= n; i++) dp[1][i] = m;
printf("Case #%d: %lld\n", cas++, f(m ,n));
}
return 0;
}

【DP】组合数字的更多相关文章

  1. n全排列输出和 n个数的组合&lpar;数字范围a~b&rpar;

    n全排列输出: int WPermutation(int num, bool bRepeat) num表示num全排列 bRepeat标志是否产生重复元素的序列. int Permutation(in ...

  2. hdu 4945 2048 (dp&plus;组合的数目)

    2048 Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submi ...

  3. &num;DP&num; ----- OpenJudge数字组合

    OpenJudge 2985:数字组合 总时间限制:1000ms  内存限制: 65536kB 描述 有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式.如:n=5,5个数分别为1,2,3, ...

  4. ZOJ-3380 Patchouli’s Spell Cards DP&comma; 组合计数

    题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3380 题意:有m种不同的元素,每种元素都有n种不同的相位,现在假 ...

  5. 3&period;29省选模拟赛 除法与取模 dp&plus;组合计数

    LINK:除法与取模 鬼题.不过50分很好写.考虑不带除法的时候 其实是一个dp的组合计数. 考虑带除法的时候需要状压一下除法操作. 因为除法操作是不受x的大小影响的 所以要状压这个除法操作. 直接采 ...

  6. CF 258B Little Elephant and Elections &lbrack;dp&plus;组合&rsqb;

    给出1,2,3...m 任取7个互不同样的数a1,a2,a3,a4,a5,a6,a7 一个数的幸运度是数位上4或7的个数 比方244.470幸运度是2. 44434,7276727.4747,7474 ...

  7. bzoj3622已经没有什么好害怕的了 dp&plus;组合&plus;容斥&lpar;&quest;&rpar;

    3622: 已经没有什么好害怕的了 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 1033  Solved: 480[Submit][Status][ ...

  8. 数位dp——奏响数字数位的美妙乐章

    数位dp:处理数字数位关系的一种dp方式. 一般的题目特征十分明显: 1.一般和数字本身有很大关系. 2.一般求数字在区间L,R中的一些信息 3.L,R一般很大,通常能达到long long级别. d ...

  9. HihoCoder 1075 开锁魔法III(概率DP&plus;组合)

    描述 一日,崔克茜来到小马镇表演魔法. 其中有一个节目是开锁咒:舞台上有 n 个盒子,每个盒子中有一把钥匙,对于每个盒子而言有且仅有一把钥匙能打开它.初始时,崔克茜将会随机地选择 k 个盒子用魔法将它 ...

随机推荐

  1. nginx源码分析之模块初始化

    在nginx启动过程中,模块的初始化是整个启动过程中的重要部分,而且了解了模块初始化的过程对应后面具体分析各个模块会有事半功倍的效果.在我看来,分析源码来了解模块的初始化是最直接不过的了,所以下面主要 ...

  2. Eclipse下配置javaweb项目快速部署到tomcat

    用惯了VS,再用Eclipse,完全有一种从自动挡到手动挡的感觉啊. 很多同学在Eclipse下开发web项目,每一次修改代码,看效果的时候都有右键项目->Run as -> Run on ...

  3. Windows Azure Web Site &lpar;10&rpar; Web Site测试环境

    <Windows Azure Platform 系列文章目录> 我们知道,在使用Azure Cloud Service的时候,会有2个不同的环境,称为Production环境和Stagin ...

  4. 洛谷P3378 【模板】堆

    P3378 [模板]堆 160通过 275提交 题目提供者HansBug 标签 难度普及- 提交  讨论  题解 最新讨论 经实际测试 堆的数组开3000- 题目有个问题 为什么这个按课本堆标准打的- ...

  5. Linus:利用二级指针删除单向链表

    Linus大神在slashdot上回答一些编程爱好者的提问,其中一个人问他什么样的代码是他所喜好的,大婶表述了自己一些观点之后,举了一个指针的例子,解释了什么才是core low-level codi ...

  6. Ubuntu搜狗输入法的使用

    下载搜狗拼音输入法安装包 删除ibus,确认没有以ibus开头的包存在 sudo dpkg -P ibus ibus-gtk ibus-gtk3 ibus-pinyin ibus-pinyin-db- ...

  7. Strust2最基本使用

    制作一个登陆表单,然后在另一个页面显示提交的内容,简单的一个小工程. 页面: //login.jsp <form action="login.action" method=& ...

  8. 微软IIS服务器的最佳优化工具- IIS Tuner

      dudu的 <让Windows Server 2008 + IIS 7+ ASP.NET 支持10万个同时请求>,里面涉及到需要手工调整参数的地方.在这篇文章中,我们给你介绍一个IIS ...

  9. mac中如何卸载pkg包

    ---恢复内容开始--- 参考地址.https://blog.csdn.net/play_fun_tech/article/details/27964861?utm_source=tuicool&am ...

  10. SQLServer修改数据列

    修改数据列 在开发和生产过程中,列名的拼写错误或者列名的更改是需要操作数据表的,大多数情况下都是不需要修改的. 以下几种情况下我们并不能直接修改数据列: 1.用于索引的列. 2.用于 CHECK.FO ...