noi.ac #528 神树和排列

题目链接：戳我

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

#define MAXN 8010

#define mod 1000000007

#define ll long long

int n,m,a[MAXN],flag[MAXN],cnt[MAXN],f[2][MAXN],sum[MAXN];

int main()

{

	#ifndef ONLINE_JUDGE

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

	#endif

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

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

	{

		int x,y;

		scanf("%d%d",&x,&y);

		if(a[x]){puts("0");return 0;}

		if(flag[y]){puts("0");return 0;}

		if(y==n&&x!=n){puts("0");return 0;}

		if(x==n&&y!=n){puts("0");return 0;}

		a[x]=y;flag[y]=1;//a[x]=y表示位置x预定的是y

	}

	//f[i][j]表示统计到前i位，其中最大的是j的方案数

        //根据题目中的排序规则，最大的一定在最右边

	for(int i=1;i<=n;++i) cnt[i]=cnt[i-1]+flag[i];

	f[0][0]=1;

	for(int i=0;i<=n;++i) sum[i]=1;

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

	{

		int now=i&1,pre=now^1;

		memset(f[now],0,sizeof(f[now]));

		//j一定在第i位

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

		{

			if(!a[i-1])//i-1的位置没有被预定

			{

				f[now][j]=((f[now][j]+1ll*f[pre][j]*(j-(i-1)-cnt[j-1])%mod)%mod+sum[j-1])%mod;

				//乘上的系数是该位可以放哪些值

			}

			else if(j>a[i-1])//如果i-1的位置被预定了，且j大于i-1位置预定的值

				f[now][j]=(f[pre][j]+f[pre][a[i-1]])%mod;

		}

		sum[i-1]=0;

		for(int j=i;j<=n;++j) sum[j]=(sum[j-1]+(flag[j]?0:f[now][j]))%mod;

		//sum[j]表示以1...j为最大的值的前缀和

		//如果这个位置被预定了，那么就是0，如果没有，就加上这一位的值

		if(a[i])//如果这个位置被预定了

		{

			flag[a[i]]=0;//a[i]这个数没有预定了，以消除后面统计前缀和的影响

			for(int j=a[i];j<=n;++j) --cnt[j];//cnt[j]表示前j大的数已经被放了几个了,同上

		}

	}

	printf("%d\n",f[n&1][n]);

	return 0;

}
巴特西

noi.ac #528 神树和排列

题目链接：戳我

最新文章

热门文章
