10个球放10个盒子

有n个球和n个盒子，编号为1, 2, 3, ... n；

一个盒子放一个球，k球不能放入k盒；

共有几种放法？

想象一下，a球放b盒，b球放c盒，c球放d盒，如此下去，必定是一个环或者多个环，且是一个有向图。

假设n=4，则一下情况都是满足的：

1->2, 2->3, 3->4, 4->1;（单环）

1->3, 3->2, 2->4, 4->1;（单环）

1->4, 4->1, 2->3, 3->2;（两个环）

因为一个盒子只能放一个球，所以不可能有a->b, a->c和a->c, b->c的情况，即有向图只能是环。

因为相同号的盒子不能放球，所以每个环至少有两个节点。

解决思路：动态规划

f(i)表示i个球有f(i)种方法；

另f(0) = 1, f(1) = 0;

f(2) = 1;(1->2, 2->1)

f(3) = 2;(1->2, 2->3, 3->1; 1->3, 3->2, 2->1)

.

.

.

f(n+1) = C(n,1)*A(1,1)*f(n-1) + C(n,2)*A(2,2)*f(n-2) + ... + C(n,k)*A(k, k)*f(n-k) + ... + C(n,n)*A(n,n)*f(n-n)

对于n+1号球，它可以与1个球组成2环，与2个球组成3环，。。。与n个球组成n+1环，这是它的所有情况了；

与k个球组成k+1环时：

我们先从前n个球任意取k个球C(n, k)；

n+1号球与这k个球组成一个环，共有A(k,k)种情况，注意不是A(k+1, k+1)，假如四个球排一个环(1->2, 2->3, 3->4, 4->1和4->1, 1->2, 2->3, 3->4是一样的)；

然后剩下n-k个球有f(n-k)种情况。

所以n+1号球在一个k+1环里共有C(n,k)*A(k,k)*f(n-k)中情况。

ps：当k=n-1时，此时n+1号球是组成了n环，剩下一个球，这是不符合的，不过前面我们已经定义f(1)=0，所以转换方程是没问题的。

#include <string.h>
#include <iostream>
using namespace std;

int factorial(int n) {
    int i = n;
    if(n <= 1)
        return 1;
    while(i > 1) {
        --i;
        n *= i;
    }
    return n;
}

int A(int n, int m) {
    return factorial(n)/factorial(n - m);
}

int C(int n, int m) {
    return A(n, m)/factorial(m);
}

int f(int n, int *dp) {
    int i, j;
    dp[0] = 1;
    dp[1] = 0;
    for(i = 2; i <= n; ++i) {
        dp[i] = 0;
        for(j = 1; j < i; ++j) {
            dp[i] += C(i - 1, j) * A(j, j) * dp[i - 1 - j];
        }
    }
    return 0;
}

int main() {
    int *dp;
    int n;
    int i;
    cout << "input:";
    cin >> n;
    dp = new int[n + 1];
    f(n, dp);
    for(i = 0; i <= n; ++i) {
        cout << i << ":" << dp[i] << endl;
    }
    delete [] dp;
    return 0;
}