0x5C 计数类DP

cf 559C 考虑到黑色的格子很少，那么我把(1,1)变成黑色，然后按每个黑色格子接近终点的程度排序，计算黑色格子不经过另一个黑色格子到达终点的方案，对于当前的格子，要减去在它右下角的所有方案数（注意不是f值）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const LL mod=1e9+;

LL MOD(LL x){return (x%mod+mod)%mod;}

LL jc[],inv[];

LL quick_pow(LL A,LL p)

{

    LL ret=;

    while(p!=)

    {

        if(p%==)ret=(ret*A)%mod;

        A=(A*A)%mod;p/=;

    }

    return ret;

}

LL getC(int n,int m){return jc[m]*inv[m-n]%mod*inv[n]%mod;}

struct node{int x,y;}a[];

bool cmp(node n1,node n2){return n1.x+n1.y>n2.x+n2.y;}

LL f[];

int main()

{

    jc[]=,inv[]=;for(int i=;i<=;i++)jc[i]=(jc[i-]*i)%mod,inv[i]=quick_pow(jc[i],mod-);

    int n,m,K;

    scanf("%d%d%d",&n,&m,&K);

    for(int i=;i<=K;i++)

        scanf("%d%d",&a[i].x,&a[i].y);

    a[++K].x=,a[K].y=;

    sort(a+,a+K+,cmp);

    for(int i=;i<=K;i++)

    {

        f[i]=getC(n-a[i].x,(n+m)-(a[i].x+a[i].y));

        for(int j=;j<i;j++)

            if(a[i].x<=a[j].x&&a[i].y<=a[j].y)

            {

                f[i]=MOD( f[i]-MOD(f[j]*getC(a[j].x-a[i].x,(a[j].x+a[j].y)-(a[i].x+a[i].y))) );

            }

    }

    printf("%I64d\n",f[K]);

    return ;

}

cf 559C

poj1737 口胡一波题解，我们知道n个点的无向图个数有2^(n*(n-1)/2)个，那么就去算不联通的，假设存在有一个包括点1的块大小为k，剩下的就是n-k个点的无向图个数了。

poj1037 其实可以借鉴一下康托展开的思想的。。。对于当前位应该选取最大的那个剩下位方案数少于m的，那么方案数就要用DP维护了。设f[i][j][k]表示枚举到第几位，选的是当前排第j的，是高位还是低位。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

LL f[][][];

void initf()

{

    f[][][]=f[][][]=;

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

        for(int j=;j<=i;j++)

        {

            for(int k=j;k<=i-;k++)f[i][j][]+=f[i-][k][];

            for(int k=;k<=j-;k++)f[i][j][]+=f[i-][k][];

        }

}

bool v[];

int main()

{

    initf();

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;LL m;

        scanf("%d%lld",&n,&m);

        memset(v,false,sizeof(v));

        int x,k;

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

        {

            if(f[n][j][]>=m){x=j,k=;break;}

            else m-=f[n][j][];

            if(f[n][j][]>=m){x=j,k=;break;}

            else m-=f[n][j][];

        }

        v[x]=true;printf("%d",x);

        for(int i=;i<=n;i++)

        {

            k^=; int j=;

            for(int y=;y<=n;y++)

            {

                if(v[y]==true)continue;

                j++;

                if((k==&&y<x)||(k==&&y>x))

                {

                    if(f[n-i+][j][k]>=m){x=y;break;}

                    else m-=f[n-i+][j][k];

                }

            }

            v[x]=true;printf(" %d",x);

        }

        printf("\n");

    }

    return ;

}

poj1037

巴特西

0x5C 计数类DP

最新文章

热门文章