Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:
Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.
To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.
Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)
However, these passwords are not possible:
1357 // There is no fingerprint on key '1'
3355 // There is fingerprint on key '7',
so '7' must occur at least once.
357 // Eve knows the password must be a 4-digit number.
With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).
Input
The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7).
Limits
Small dataset
T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset
T = 100.
1 ≤ M ≤ N ≤ 100.
Sample
Input
4
1 1
3 4
5 5
15 15
Output?
Case #1: 1
Case #2: 36
Case #3: 120
Case #4: 674358851
google在線筆試題。這題一直沒做出來。有人說有公式，看到大牛們提交的代碼又覺得像是dp。后來學了生成函數之后，覺得應該是一道指數型生成函數的題。
1
#include <iostream>
2
#include <cstdio>
3
#include <vector>
4
5
using
namespace
std;
6
const
double
epi =
0.000001
;
7
int
frac(
int
k) {
8
int
ans =
1
;
9
for
(
int
i =
2
; i <= k; ++
i) {
10
ans *=
i;
11
}
12
return
ans;
13
}
14
15
int
enumPassword(
int
n,
int
m) {
16
vector<vector<
double
> >
params
(
2
, vector<
double
>(n +
1
,
0
));
17
params
[
0
][
0
] =
1
;
18
int
cur =
0
, next =
1
;
19
20
for
(
int
i =
0
; i < m; ++
i) {
21
params
[next].assign(n +
1
,
0
);
22
for
(
int
j =
0
; j <= n; ++
j) {
23
if
(
params
[cur][j] < epi)
continue
;
24
for
(
int
k =
1
; k + j <= n; ++
k) {
25
params
[next][k + j] =
params
[next][k + j] +
params
[cur][j] *
1
/
frac(k);
26
}
27
}
28
cur = !cur; next = !
next;
29
}
30
31
return
params
[cur][n] *
frac(n);
32
}
33
34
int
main(
int
argc,
char
**
argv) {
35
if
(argc <
2
)
return
-
1
;
36
freopen(argv[
1
],
"
r
"
, stdin);
37
int
test;
38
scanf(
"
%d
"
, &
test);
39
for
(
int
i =
0
; i < test; ++
i) {
40
int
m, n;
41
scanf(
"
%d%d
"
, &m, &
n);
42
cout <<
"
Case #
"
<< i +
1
<<
"
:
"
<< enumPassword(n, m) <<
endl;
43
}
44
45
return
0
;
46
}
但是數太大，要取模。除操作不能直接除模。
在網上搜到一個定理：
定理12.2：設$a_n$,$b_n$的指數生成函數分別為f(x)和g(x)，則：
$f(x)*g(x) = \sum_{n=0}^{\infty}c_n\frac{x^n}{n!}, c_n = \sum_{k=0}^{n}C(n,k)a_kb_{n-k}$。
對應到我們這里，Line 25里就變成params[cur][j]*1*C(j+k, k)，params[cur][j]對應的是$\frac{x^j}{j!}$的系數，1對應的是$\frac{x^k}{k!}$，所以乘以的就是C(j+k, k)了。
代碼如下：
1
#include <iostream>
2
#include <cstdio>
3
#include <vector>
4
5
using
namespace
std;
6
enum
{MOD =
1000000007
};
7
typedef
long
long
llong;
8
llong combination[
100
][
100
];
9
void
getCombination() {
10
for
(
int
i =
0
; i <=
100
; ++
i) {
11
for
(
int
j =
0
; j <= i; ++
j) {
12
if
(j ==
0
) {
13
combination[i][j] =
1
;
14
}
else
{
15
combination[i][j] = (combination[i -
1
][j] + combination[i -
1
][j -
1
]) %
MOD;
16
}
17
}
18
}
19
}
20
21
llong enumPassword(
int
n,
int
m) {
22
vector<vector<llong> >
params
(
2
, vector<llong>(n +
1
,
0
));
23
params
[
0
][
0
] =
1
;
24
int
cur =
0
, next =
1
;
25
26
for
(
int
i =
0
; i < m; ++
i) {
27
params
[next].assign(n +
1
,
0
);
28
for
(
int
j =
0
; j <= n; ++
j) {
29
if
(
params
[cur][j] ==
0
)
continue
;
30
for
(
int
k =
1
; k + j <= n; ++
k) {
31
params
[next][k + j] = (
params
[next][k + j] +
params
[cur][j] * combination[j + k][k]) %
MOD;
32
}
33
}
34
cur = !cur; next = !
next;
35
}
36
37
return
params
[cur][n];
38
}
39
40
int
main(
int
argc,
char
**
argv) {
41
if
(argc <
2
)
return
-
1
;
42
freopen(argv[
1
],
"
r
"
, stdin);
43
if
(argc >=
3
) freopen(argv[
2
],
"
w
"
, stdout);
44
getCombination();
45
int
test;
46
scanf(
"
%d
"
, &
test);
47
for
(
int
i =
0
; i < test; ++
i) {
48
int
m, n;
49
scanf(
"
%d%d
"
, &m, &
n);
50
//
cout << "Case #" << i + 1 << ": " << enumPassword(n, m) << endl;
51
printf(
"
Case #%d: %lld\n
"
, i +
1
, enumPassword(n, m));
52
}
53
54
return
0
;
55
}
注意這里求組合數要用遞推公式來求，這樣可以在運算中取模，避免溢出。
$C(n, m) = C(n - 1, m) + C(n - 1, m - 1)$。
以后指數型生成函數的題都可以這么做。get！
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
