正文
[GCJ]Password Attacker
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
https://code.google.com/codejam/contest/4214486/dashboard#s=p0
排列组合。DP递推式，如下代码。dp[m][n]表示长度为n的字符串里有m个字符，那么可以先用m-1个字符拼一个长度为n-1的字符串，然后再C(n,1)里面挑一个放最后一个字符;这是最后一种字符是一个的情况，后面还有两个三个等等。所以代码如下：
要注意的是，可以先计算组合数combination[n][m]，用C(n,m)=C(n−1,m)+C(n−1,m−1)来算。
/*
f[i][n] = f[i-1][n-1]*C(n,1) + f[i-1][n02]*C(n,2) + ... + f[i-1][i-1] * C(n, n-(i-1));
*/#include <iostream>
#include <vector>
using namespace std;int base = 1000000007;
typedef long long llong;llong combination[101][101];void buildCombination() {
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
combination[i][j] = 1;
} else {
combination[i][j] = (combination[i-1][j] + combination[i-1][j-1]) % base;
}
}
}
}llong solve(int m, int n) {
vector<vector<llong> > dp;
dp.resize(m+1);
for (int i = 0; i < m+1; i++) {
dp[i].resize(n+1);
}
// i chars, len of j
for (int i = 1; i <= m; i++) {
for (int j = i; j <= n; j++) {
if (i == 1) {
dp[i][j] = 1;
continue;
}
dp[i][j] = 0;
for (int k = 1; j-k >= i-1; k++) {
dp[i][j] = (dp[i][j] + dp[i-1][j-k] * combination[j][k]) % base; }
}
}
return dp[m][n];
}int main() {
int T;
buildCombination();
cin >> T;
for (int i = 1; i <= T; i++) {
int m, n;
cin >> m >> n;
llong r = solve(m, n);
cout << "Case #" << i << ": " << r << endl;
}
return 0;
}
