「日常训练」 神、上帝以及老天爷 （HDU 2048）

题意

数论中的错排问题。记错排为Dn" role="presentation">DnDn，求Dnn!" role="presentation">Dnn!Dnn!。

分析

显然D1=0,D2=1" role="presentation">D1=0,D2=1D1=0,D2=1。当n≥3" role="presentation">n≥3n≥3时，不妨设n排在了第k位，其中k≠n" role="presentation">k≠nk≠n，也就是1≤k≤n−1" role="presentation">1≤k≤n−11≤k≤n−1。那么我们现在考虑k的情况。

• 当k排在第n位时，n放k、k放n确定，因而除了n和k以外还有n-2个数，其错排数为Dn−2" role="presentation">Dn−2Dn−2。
• 当k不排在第n位时，由于n在第k位，那么将第n位重新考虑成一个新的“第k位”，那么注意到“n在k”是确定的。剩下的排布方式同原来一致，只是k等价于n，因此：其错排数为Dn−1" role="presentation">Dn−1Dn−1。
  我们认真思考一下这个“重新考虑”是什么意思。 n在k，这是一个固定的条件，故这里不作考虑；而其他的元素必定不在各自的位置，k也是：它必定不在n！因而，这里相当于n−1" role="presentation">n−1n−1个元素的错排问题。

综上，当n" role="presentation">nn排在第k" role="presentation">kk位时共有Dn−2+Dn−1" role="presentation">Dn−2+Dn−1Dn−2+Dn−1种错排方法，又k" role="presentation">kk有从1" role="presentation">11到n−1" role="presentation">n−1n−1共n−1" role="presentation">n−1n−1种取法，我们可以得到：Dn=(n−1)(Dn−1+Dn−2)" role="presentation">Dn=(n−1)(Dn−1+Dn−2)Dn=(n−1)(Dn−1+Dn−2)

更多其他方法另请参见一位不愿具名的同学的题解。

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#define inf 0x3f3f3f3f

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define lowbit(x) (x & (-x))

#define rep(i, a, b) for (int i = (a); i <= (b); i++)

#define per(i, a, b) for (int i = (a); i >= (b); i--)

#define pr(x) cout << #x << " = " << x << " ";

#define prl(x) cout << #x << " = " << x << endl;

#define ZERO(X) memset((X), 0, sizeof(X))

#define ALL(X) (X).begin(), (X).end()

#define SZ(x) (int)x.size()

using namespace std;

typedef pair<int, int> PI;

typedef pair<pair<int, int>, int> PII;

typedef pair<pair<pair<int, int>, int>, int> PIII;

using ull = unsigned long long;

using ll = long long;

using ld = long double;

#define quickio                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0)

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

/*      debug("Precalc: %.3f\n", (double)(clock()) / CLOCKS_PER_SEC);

clock_t z = clock();

        solve();

        //debug("Test: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);

*/

template <typename T = int>

inline T read()

{

    T val = 0, sign = 1;

    char ch;

    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())

        if (ch == '-')

            sign = -1;

    for (; ch >= '0' && ch <= '9'; ch = getchar())

        val = val * 10 + ch - '0';

    return sign * val;

}

int main()

{

    ll arr[25];

    arr[1] = 0;

    arr[2] = 1;

    ll jc[25];

    jc[1] = 1;

    jc[2] = 2;

    for (int i = 3; i <= 20; ++i)

    {

        arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2]);

        jc[i] = jc[i - 1] * i;

    }

    int T;

    cin >> T;

    while (T--)

    {

        int n;

        cin >> n;

        cout << fixed << setprecision(2)

             << double(arr[n]) * 100.0 / jc[n]  << "%" << endl;

    }

    return 0;

}

修改于20180524，进一步方便自己回顾对错排问题的理解。