BZOJ-4563: [Haoi2016]放棋子

Description

给你一个N * N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。 n<=2000

等价于每一列只能选择一行所对应，所对应的行不重复，并且每一列都有一行不能选，同样也不重复，等价于：错排问题：f[i]=(f[i-1]+f[i-2]) * (i-1);
外加个高精度就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=100000000000000ll;
struct precision
{
    ll w[1000];
    int t;
    precision(){memset(w,0,sizeof w); t=0;}
    precision operator +(const precision z)
    {
        precision re; re.t=max(t,z.t); ll yu=0;
        for(int i=1;i<=re.t;++i)
        {
            (w[i]+z.w[i]+yu>=mod) ? (re.w[i]=w[i]+z.w[i]+yu-mod,yu=1) :
            (re.w[i]=w[i]+z.w[i]+yu,yu=0);
        }
        if(yu) re.w[++re.t]=yu;
        return re;
    }
    precision operator *(const ll z)
    {
        precision re; re.t=t; ll yu=0;
        for(int i=1;i<=t;++i)
        {
            re.w[i]=(w[i]*z+yu)%mod;
            yu=(w[i]*z+yu)/mod;
        }
        while(yu) re.w[++re.t]=yu%mod,yu/=mod;
        return re;
    }
    void print()
    {
        printf("%lld",w[t]);
        for(int i=t-1;i>=1;--i) printf("%014lld",w[i]);
    }
}f[2010];
int main()
{
    int n; scanf("%d",&n);
    f[0].t=1; f[0].w[1]=1;
    for(int i=2;i<=n;++i) f[i]=(f[i-1]+f[i-2])*(i-1);
    f[n].print();
    return 0;
}