Problem E

MIXING INVITATIONS

Kelly is having a birthday party soon, and would like to invite all her friends to come. There is one problem though: her house is far too small to accommodate everyone! She has already written up personalised invitations to all her friends with corresponding addressed envelopes to mail them in, and now she doesn't know what to do.

Luckily, Alex has thought of a clever way to help Kelly out. He knows that if a friend receives an invitation personalised to him or her, that friend will definitely come to the party. However, if a friend receives an invitation personalised to someone else (ie. the wrong invitation), that friend will surely not come to the party. Alex then goes to mix up Kelly's invitations and envelopes so that some invitations may be mailed to the wrong addressee. This way everyone still gets an invitation and nobody is left out, but no more people would come than would fit into Kelly's house.

There are exactly as many envelopes as there are invitations, and each invitation has a corresponding envelope with the same addressee. Alex must place each invitation into an envelope in such a way that there are no more invitations in their correct envelopes than the amount of people Kelly can accommodate.

Being the clever mathematician that he is, Alex would like to count the number of ways that he can mix up the invitations and envelopes to accomplish his goal. Can you write a program to do this for Alex?

Input

The input file contains several test cases, each on a separate line. Each line contains two positive integers, N and M, separated by a space. N (1 ≤ N ≤ 20) is the number of invitations Kelly has written, and M (0 ≤ M ≤ N) is the maximum number of people Kelly can accommodate.

Output

For each test case, output on a separate line a single integer: the number of ways Alex can mix up the invitations and envelopes to accomplish his goal.

Sample Input

3 2
4 1
4 4

Output for the Sample Input

5
17
24

---

Daniel Adler
Calgary Collegiate Programming Contest 2006

題目描述：

有 n 個人，n 個信封。如果放入信封內的內容正確，則可以正常邀請該人。

由於寫給每個人的內容都不同，因此只會存在 1 種邀情所有的人。

問最多邀請 m 個人的可能有多少種？

題目解法：

考慮恰好邀請 i 個人會來，那麼剩餘的人剛好都拿到不是自己想要的內容，

也就是錯排，上網可以搜尋"錯排公式"。


#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    long long dp[105], C[105][105] = {};
    int i, j, k;
    int n, m;
    dp[0] = 1, dp[1] = 0;
    for(i = 2; i < 100; i++)
        dp[i] = (i-1)*(dp[i-1] + dp[i-2]);
    C[0][0] = 1;
    for(i = 1; i < 100; i++) {
        C[i][0] = 1;
        for(j = 1; j <= i; j++)
            C[i][j] = C[i-1][j]+C[i-1][j-1];
    }
    while(scanf("%d %d", &n, &m) == 2) {
        long long ret = 0;
        for(i = 0; i <= m; i++)
            ret += C[n][i]*dp[n-i];
        printf("%lld\n", ret);
    }
    return 0;
}