正解:$dp$

解题报告:

传送门$QwQ$

首先港下不合法的情况.设$sum_i$表示$q\geq i$的人数,当且仅当$sum_i>n-i+1$时无解.

欧克然后考虑这题咋做$QwQ$.

一般的想法是枚人然后考虑给他啥编号.但是发现这样好像不太可做,所以考虑换一种思考方式.

考虑设$f_{i,j}$表示对于没安排的有$j$个人编号小于等于$i$的方案数

然后考虑转移,发现就枚给多少个人编号$i$就成.于是转移就$f_{i,j}=\sum f_{i+1,k}\cdot C(n-m-k,j-k).$

嗷然后补一个点$kk$.

就因为那个$mod$没有限制所以不能预处理阶乘逆元地搞,但是因为$n$的范围很小所以可以直接预处理数组$C_{i,j}$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define lf double

#define gc getchar()

#define t(i) edge[i].to

#define n(i) edge[i].nxt

#define w(i) edge[i].wei

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];~i;i=n(i))

const int N=300+10;

int n,m,mod,f[N][N],sum[N],jc[N],inv[N],C[N][N];

il int read()

{

    rc ch=gc;ri x=0;rb y=1;

    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;

    if(ch=='-')ch=gc,y=0;

    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;

    return y?x:-x;

}

il void ad(ri &x,ri y){x+=y;if(x>=mod)x-=mod;}

il void pre(){rp(i,0,n){C[i][0]=1;rp(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}}

il void solv()

{

    memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));

    n=read();m=read();mod=read();pre();rp(i,1,m){read();++sum[read()];}

    my(i,n,1){sum[i]+=sum[i+1];if(sum[i]>n-i+1){printf("NO\n");return;}}

    f[n+1][0]=1;

    my(i,n+1,1)

    {

        rp(j,0,n-sum[i]-i+1)

        {

            rp(k,0,min(j,n-sum[i+1]-(i+1)+1))

                ad(f[i][j],1ll*f[i+1][k]*C[n-m-k][j-k]%mod);//,

            //printf("f[%d][%d]+=f[%d][%d]*%d C[%d][%d]=%d\n",i,j,i+1,k,C[n-m-k][j-k],n-m-k,j-k,C[n-m-k][j-k]);

        }

    }

    printf("YES %d\n",f[1][n-m]);

}

int main()

{

    freopen("2523.in","r",stdin);freopen("2523.out","w",stdout);

    ri T=read();while(T--)solv();

    return 0;

}

巴特西

洛谷$P2523\ [HAOI2011]\ Problem\ c$ $dp$

正解:$dp$

解题报告:

最新文章

热门文章