首页 > 资讯 > 其他 > 正文

51nod 1327 棋盘游戏

17-06-20 来源：[db:作者]

收藏我要投稿

有一个N行M列的棋盘，即该棋盘被分为N*M格。现在向棋盘中放棋子，每个格子中最多放一个棋子，也可以一个不放。放完棋子后需要满足如下要求：

1）对于第i行来说，其从左往右的前left[i] 个格子（即最左侧的left[i] 个连续的格子）中恰好一共有1个棋子；

2）对于第i行来说，其从右往左的前right[i]个格子（即最右侧的right[i]个连续的格子）中恰好一共有1个棋子；

3）对于每一列来说，这一列上的所有格子内含有的棋子数不得超过1个。

其中，1）与2）条件中，对所有 i 满足 left[i]+right[i] <= M，即两个区间不会相交。

问，符合上述条件情况下棋子的不同放法一共有多少种？输出放法的个数 mod 1,000,000,007后的结果。

例如样例中，只有如下图一种方法。

Input

第一行包含两个整数，N，M，其中1<=N<=50,2<=M<=200.
之后有N行，每行两个数left[i],right[i],其中，1<=left[i],right[i]<=M,且left[i]+right[i]<=M。

Output

一个整数，即符合条件的方案数mod1,000,000,007后的结果。

Input示例

24
12
21

Output示例

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

神奇DP+思路~

用fi][j][k]表示当前i列，有j列没有放棋子，k行的right不满足。那么我们为了满足left，就要在更新的时候记录已经有多少left，强制更新。

为了节省时间可以把a排序。

数组开小了WAWAWA……2333

#include
#include
#include
#include
using namespace std;
#define mod 1000000007
#define ll long long

int n,m,f[202][202][52],c[202][202],mi[202],ans,l,r,block;

struct node{
	int l,r;
}a[51];

bool operator < (node u,node v)
{
	return u.l==v.l ? u.r<>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

void add(int &a,int b)
{
	a+=b;
	if(a>=mod) a-=mod;
}

int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=m-read()+1;
	sort(a+1,a+n+1);
	for(int i=0;i<=201;i++) c[i][0]=1;
	for(int i=1;i<=201;i++)
	  for(int j=1;j<=i;j++) add(c[i][j],c[i-1][j]+c[i-1][j-1]);
	mi[0]=1;
	for(int i=1;i<=201;i++) mi[i]=(ll)mi[i-1]*i%mod;
	for(int i=1;i<=201;i++)
	  for(int j=1;j<=i;j++) c[i][j]=(ll)c[i][j]*mi[j]%mod;
	f[0][0][0]=1;
	for(int i=0;ii+1);
		for(int j=l-1;j<=i+1;j++)
		  for(int k=0;k<=n-r;k++)
		  {
		  	if(j+1>=l && l>=1) add(f[i+1][j+1-l][k+r],(ll)l*c[j][l-1]%mod*f[i][j][k]%mod);
		  	if(j>=l)
		  	{
		  		add(f[i+1][j+1-l][k+r],(ll)c[j][l]*f[i][j][k]%mod);
		  		if(k+r>=1) add(f[i+1][j-l][k+r-1],(ll)c[j][l]*f[i][j][k]%mod*(k+r)%mod);
		  		if(block) add(f[i+1][j-l][k+r],(ll)c[j][l]*f[i][j][k]%mod*block%mod);
		  	}
		  }
	}
	for(int i=0;i<=m;i++) add(ans,f[m][i][0]);
	printf("%d\n",ans);
	return 0;
}

点击复制链接与好友分享!回本站首页