小y的容器

NC231111. 小y的容器

描述

求将 $1-n$ 这 $n$ 个数放入三个容器中使得容器中的数排序以后相邻两个之差小于等于 $3$ 的方案数（要保证任意容器中至少有一个数且每个数必须放入一个容器中）

例如某个容器中的数若是 $[3,5,6]$ 则是合法的，若是 $[1,5,6]$ 则不合法，原因是 $1,5$ 的差超过了 $3$

其中有 $m$ 个限制 $x,y$ 代表 $x$ 不能放在 $y$ 这个容器中，答案对 $10^9+7$ 取模

两个方案不同当且仅当两个方案中至少有一个数所在的容器不同

输入描述

第一行两个正整数

接下来行每行个数

输出描述

输出一行一个数代表答案

示例1

输入:

4 1
1 2

输出:

说明:

对于样例[1][2][3,4]是一种合法方案,[1,2][3,4][]是不合法的，因为出现了空的序列，[2][1,3][4]是不合法的，因为1不能放在第二个容器中

示例2

输入:

输出:

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

C++ 解法, 执行用时: 12ms, 内存消耗: 10260K, 提交时间: 2022-02-25 02:18:31

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define M 1000000007
int i,j,k,l,n,m,t,j1,k1,l1;
ll f[10050][5][5][5],res;
bool sb[10500][5];
int main() {
	memset(sb,1,sizeof(sb));
	ios::sync_with_stdio(0);
	cin>>n>>t;
	while(t--){cin>>i>>j;sb[i][j]=0;}
	f[0][0][0][0]=1;
	for(i=0;i<=n;i++)for(j=0;j<=4;j++)for(k=0;k<=4;k++)for(l=0;l<=4;l++){
		ll t=f[i][j][k][l]%M;
		j1=(j>0&&j<4);k1=(k>0&&k<4);l1=(l>0&&l<4);
		if(i==n)res+=t*(j&&k&&l);
		f[i+1][1][k+k1][l+l1]+=t*sb[i+1][1]*(j<=3);
		f[i+1][j+j1][1][l+l1]+=t*sb[i+1][2]*(k<=3);
		f[i+1][j+j1][k+k1][1]+=t*sb[i+1][3]*(l<=3);
	}
	cout<<res%M;
}