# Problem A. Password Attacker ### Source - [Dashboard - Round B APAC Test - Problem A. Password Attacker](https://code.google.com/codejam/contest/4214486/dashboard#s=p0) ### Problem 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. #### Smaple ~~~ Input Output 4 1 1 Case #1: 1 3 4 Case #2: 36 5 5 Case #3: 120 15 15 Case #4: 674358851 ~~~ ### 題解 題目看似很長，其實簡單來講就是用 M 個 不同的字符組成長度為 N 的字符串，問有多少種不同的排列。這里 M 小于 N，要是大于的話就是純排列了。這道題我最開始想用純數學方法推導公式一步到位，實踐下來發現這種想法真是太天真了，這不是數學競賽... 即使用推導也應該是推導類似動態規劃的狀態轉移方程。 這里的動態規劃不太明顯，我們以狀態`dp[m][n]`表示用 m 個不同的字符能組成長度為 n 的不同字符串的個數。這里需要注意的是最后長度為 n 的字符串中必須包含 m 個不同的字符，不多也不少。接下來就是尋找狀態轉移方程了，之前可能的狀態為`dp[m - 1][n -1], dp[m - 1][n], dp[m][n - 1]`. 現在問題來了，怎么解釋這些狀態以尋找狀態轉移方程？常規方法為正向分析，即分析`m ==> n`, 但很快我們可以發現`dp[m - 1][n]`這個狀態很難處理。既然正向分析比較麻煩，我們不妨試試反向從`n ==> m`分析，可以發現字符串個數由 n 變為 n-1，這減少的字符可以分為兩種情況，一種是這個減少的字符就在前 n - 1個字符中，另一種則不在，如此一來便做到了不重不漏。相應的狀態轉移方程為： ~~~ dp[i][j] = dp[m][n-1] * m + dp[m - 1][n - 1] * m ~~~ 第一種和第二種情況下字符串的第 n 位均可由 m 個字符中的一個填充。初始化分兩種情況，第一種為索引為0時，其值顯然為0；第二種則是 m 為1時，容易知道相應的排列為1。最后返回 `dp[M][N]`. ### Java ~~~ import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); // System.out.println("T = " + T); for (int t = 1; t <= T; t++) { int M = in.nextInt(), N = in.nextInt(); long ans = solve(M, N); // System.out.printf("M = %d, N = %d\n", M, N); System.out.printf("Case #%d: %d\n", t, ans); } } public static long solve(int M, int N) { long[][] dp = new long[1 + M][1 + N]; long mod = 1000000007; for (int j = 1; j <= N; j++) { dp[1][j] = 1; } for (int i = 2; i <= M; i++) { for (int j = i; j <= N; j++) { dp[i][j] = i * (dp[i][j - 1] + dp[i - 1][j - 1]); dp[i][j] %= mod; } } return dp[M][N]; } } ~~~ ### 源碼分析 Google Code Jam 上都是自己下載輸入文件，上傳結果，這里我們使用輸入輸出重定向的方法解決這個問題。舉個例子，將這段代碼保存為`Solution.java`, 將標準輸入重定向至輸入文件，標準輸出重定向至輸出文件。編譯好之后以如下方式運行： ~~~ java Solution < A-large-practice.in > A-large-practice.out ~~~ 這種方式處理各種不同 OJ 平臺的輸入輸出較為方便。 ### 復雜度分析 時間復雜度 O(mn)O(mn)O(mn), 空間復雜度 O(mn)O(mn)O(mn). ### Reference - [Google-APAC2015-"Password Attacker" - dmsehuang的專欄](http://blog.csdn.net/dmsehuang/article/details/40807799)