FZU 2282 Wand 组合数学错排公式

　　题目链接： http://acm.fzu.edu.cn/problem.php?pid=2282

　　题目描述： N个数映射N个相同数，问有几种情况至少有K个映射自己的数

　　解题思路：很裸的错排公式，之前自己想到从反面求会比较好求，但是也是到了错排公式这里，有一个点没有想到，就是分类讨论的情况二，错排公式： D(i) = (i-1) * (D(i-1) + D(i-2)), 看了一遍就很容易理解，无奈自己之前自己就是看了一眼错排公式的标题

　　代码：不知道是不是AC代码， FZU崩了

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

const ll mod =(ll) 1e9+7;
const int maxn = 20000;
ll f[maxn];
int n;
ll cp[maxn];

void init() {
    cp[1]=0;
    cp[2]=1;
    for(int i=3;i<=10000;i++)
    {
        (cp[i]=(i-1)*(cp[i-1]+cp[i-2]))%=mod;
    }
    f[0] = f[1] = 1;
    for(int i = 2; i < maxn; i++) f[i] = (f[i-1] * i) % mod;
}
ll mul(ll x, ll n) {
    ll ret = 1;
    while(n) {
        if(n & 1) ret = (ret * x) % mod;
        n >>= 1;
        x = (x * x) % mod;
    }
    return ret;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    else {
        ll ret = exgcd(b, a%b, x, y);
        ll tmp = x;
        x = y;
        y = tmp - a / b * y;
        return ret;
    }
}
ll inv(ll a) {
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}
ll C(ll x, ll y) {
    return f[x] * inv(f[x-y]) % mod * inv(f[y]) % mod;
}
//ll C(int i,int n)
//{
//    return ((f[n]*mul((f[n-i]*f[i])%mod,mod-2))%mod);
//}
int main() {
    int n, k;
    int t;
    sca(t);
    init();
//    for( int i = 1; i <= 100; i++ ) {
//        cout << cp[i] << " ";
//    }
//    cout << endl;
    while( t-- ) {
        scanf( "%d %d", &n, &k );
        ll ans = 1;
        for( int i = 2; i <= n-k; i++ ) {
            (ans+=cp[i]*C(i,n))%=mod;
        }
        printf( "%lld
", ans );
    }
    return 0;
}

View Code

　　思考：果然掌握的理论，公式越多题就能做出来，要广接触理论......

FZU 2282 Wand 组合数学 错排公式

FZU 2282 Wand 组合数学错排公式