Youhane Playing beatmania IVDX

NC15491. Youhane Playing beatmania IVDX

描述

べィスドロップ〜

周所周知，KONMAI出品的Beatmania IVDX是一款非常经典的街机音乐游戏，已经有数十年的历史。优酱最近想要开始体验这款游戏，但是她知道自己的水平实在是太差了，以至于连最低级别的段位认定都不能合格。为了让自己省一些钱（要知道因为beatmania IVDX是街机游戏，所以每玩一道至少都是需要投6块钱的），她决定自己制作一个模拟器来在家练习。

在实现这个模拟器的时候，优酱突发奇想：如果这个游戏不只有七个按键和一个转盘的话，会产生多少种具有特定排列的谱面呢？为了方便叙述，让我们把谱面抽象成一个 $n \times m$ 大小的网格（

横行，

纵列，你可以把每一列看成每一个按键，每一行看成一个时间点），行和列的编号都是从

起算的，行从上到下数到

，列从左到右数到

，棋盘的每一个格子都可以是黑色（表示有note）或者白色（没有note）。

我们定义，在满足下述全部条件的时候，谱面上出现了一个"Youhane Pattern"：

1. 存在一个闭区间 $[l,r](1 \le l \le r \le n)$ ，使得

这些行都有且仅有两个黑色格子，而铺面中的其他行不存在黑色格子。
2. 存在一个行编号 $t(l \le t \le r)$ ，使得：

* 对于任意存在黑色格子的行

，把这行的黑色格子所对应的列编号，以及黑色格子之间的那些白色格子（如果有）对应的列编号加入一个集合，我们称之为

`。
* 任取

及

之上的两个有黑色格子的行，令上方的行为

，下方的行为

，则

是

的子集。
* 任取

及

之下的两个有黑色格子的行，令上方的行为

，下方的行为

，则

是

的子集。

上面的对于“Youhane Pattern”的形式化描述可能有点过于复杂了，为了帮助你理解，优酱画了一个“Youhane Pattern”的样例：

优酱关心的是，给出谱面的大小

和

，有多少种放note的方案，使得谱面呈现“Youhane Pattern”呢？请输出方案数模

的结果。

输入描述

单文件，多数据。在文件中，每行包含两个用空格分开的整数和，其中。

输出描述

请输出题目要求的答案，独占一行。

示例1

输入:

1 1
4 4
3 5

输出:

0
485
451

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 974ms, 内存消耗: 47336K, 提交时间: 2020-04-02 22:59:59

#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[2002][2002],c[2002][4002];
int main()
{
	int i,j,s,p,q;
	for(i=0;i<=2000;i++)
	for(j=0;j<=4000;j++)
	{
		if(i==0)
		c[i][j]=1;
		else
		{
			if(i>=1)
			c[i][j]=(c[i][j]+c[i-1][j])%mod;
			if(j>=1)
			c[i][j]=(c[i][j]+c[i][j-1])%mod;
		}
	}
	while(scanf("%d%d",&n,&m)==2)
	{
		m--;
		for(i=1;i<=n;i++)
		for(j=0;j<m;j++)
		f[i][j]=(c[m-j-1][2*i-2]+f[i-1][j])%mod;
		int ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<m;j++)
			ans=(ans+1LL*f[i][j]*c[m-j-1][2*(n-i)]%mod*(j+1))%mod;
		 } 
		 printf("%d\n",ans);
	}
	return 0;
 }