BZOJ 4563: [Haoi2016]放棋子

2022-11-15 19:43:45

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 389 Solved: 248
[Submit][Status][Discuss]

Description

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在

这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子

的限制，求有多少种方案。

Input

第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例

Output

一个整数，即合法的方案数。

Sample Input

2
0 1
1 0

Sample Output

HINT

Source

交换阵法的行列对于答案是没有影响的，所以我们可以将阴阳玉都
换到对角线上，然后答案就变为了求 n 的错排数，通过递推式即可求出。

f[n]=(n-1)*(f[n-1]+f[n-2]);

高精

考试丧心病狂的数据最大到5000 需要压位高精代码底下有。

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#define N 500

#define MOD 10

inline int max(int a,int b) {return a>b?a:b;}

struct node

{

    int a[N];

    inline node operator+(node b)

    {

        node c;

        c.a[]=max(a[],b.a[])+;

        for(int i=;i<=c.a[];++i)

        {

            c.a[i]+=a[i]+b.a[i];

            c.a[i+]+=c.a[i]/MOD;

            c.a[i]=c.a[i]%MOD;

        }

        for(;c.a[]>&&c.a[c.a[]]==;c.a[]--);

        return c;

    }

    node() {memset(a,,sizeof(a));}

}ans[N];

int G[N][N],n;

node operator*(int x,node b)

{

    int t=;

    node c;

    c.a[]=b.a[]+;

    for(int i=;i<=c.a[];++i) c.a[i]=b.a[i]*x;

    for (int i=;i<=c.a[];i++)

    {

        c.a[i]+=t;

        if (c.a[i]>=MOD){t=c.a[i]/MOD;c.a[i]%=MOD;}

        else t=;

    }

    for(;t;t/=MOD) c.a[++c.a[]]=t%MOD;

    for(;c.a[]>&&c.a[c.a[]]==;c.a[]--);

    return c;

}

int Main()

{

    scanf("%d",&n);

    ans[].a[]=;ans[].a[]=,ans[].a[]=ans[].a[]=;

/*  for(int i=1;i<=n;++i)

     for(int j=1;j<=n;++j)

      scanf("%d",&G[i][j]);*/

    for (int i=;i<=n;i++) ans[i]=(i-)*(ans[i-]+ans[i-]);

    printf("%d",ans[n].a[ans[n].a[]]);

    for (int i=ans[n].a[]-;i>=;i--) printf("%d",ans[n].a[i]);

    return ;

}

int sb=Main();

int main(int argc,char *argv[]){;}

#include <cstring>

#include <cstdio>

#define N 5005

#define MOD 10000

inline int max(int a,int b) {return a>b?a:b;}

struct node

{

    int a[N];

    inline node operator+(node b)

    {

        node c;

        c.a[]=max(a[],b.a[])+;

        for(int i=;i<=c.a[];++i)

        {

            c.a[i]+=a[i]+b.a[i];

            c.a[i+]+=c.a[i]/MOD;

            c.a[i]=c.a[i]%MOD;

        }

        for(;c.a[]>&&c.a[c.a[]]==;c.a[]--);

        return c;

    }

    node()

        {memset(a,,sizeof(a));}

}ans[N];

int G[N][N],n;

node operator*(int x,node b)

{

    int t=;

    node c;

    c.a[]=b.a[]+;

    for(int i=;i<=c.a[];++i) c.a[i]=b.a[i]*x;

    for (int i=;i<=c.a[];i++)

      {

        c.a[i]+=t;

        if (c.a[i]>=MOD){t=c.a[i]/MOD;c.a[i]%=MOD;}

        else t=;

      }

    for(;t;t/=MOD) c.a[++c.a[]]=t%MOD;

    for(;c.a[]>&&c.a[c.a[]]==;c.a[]--);

    return c;

}

int Main()

{

    freopen("firstmeet.in","r",stdin);

    freopen("firstmeet.out","w",stdout);

    scanf("%d",&n);

    ans[].a[]=;ans[].a[]=,ans[].a[]=ans[].a[]=;

/*    for(int i=1;i<=n;++i)

     for(int j=1;j<=n;++j)

      scanf("%d",&G[i][j]);

*/    for (int i=;i<=n;i++) ans[i]=(i-)*(ans[i-]+ans[i-]);

    printf("%d",ans[n].a[ans[n].a[]]);

    for (int i=ans[n].a[]-;i>=;i--) printf("%04d",ans[n].a[i]);

    return ;

    fclose(stdin);

    fclose(stdout);

}

int sb=Main();

int main(int argc,char *argv[]){;}

丧心病狂的5000(压位)

码农公寓