[LNOI2022] 题

题意：

建议看原题面，抽象文字会严谨很多。
给长为\(3*n\)的字符串s,每个位置值为\([0,3]\),如果为\(0\)的话，你构造字符串\(t\),即把\(0\)替换为\([1,3]\)。如果\(t\)中每三个配对（前提是为排列，且按编号从前往后的逆序对奇数），问配出的\(n\)对的方案数，方案不同当且仅当\(t\)不同或者任意两对三个值对应下标有一个不同。

思路：

感觉自己没有创造力，\(n<=19\)以为是状压，结果是\(o(n^7)\)摩天轮大dp。
逆序对奇数，即\(132,213,321\)三种情况。
我一开始是把问题拆看看的，先构造\(t\),再看对应方案数。其实发现这种\(？\)填充问题+dp的话，都会直接在决策转移\(?\)时考虑选择，且存在同一个状态里。
该题正确的解读方式：分组(匹配)的方案数。
发现一组大小\(3\)其实很小，如果再小一点，是\(2\)呢？
一组大小为\(2\)，组中第一个加入时，加入状态。
如果大小为\(3\)，同理存第一个元素状态，（可更新前两个元素状态）因此存前两个状态，因此也可以转移第三个填入。
这道题的状态就出来了：
\(dp[i][x][y][z][o][p][q]\)：表到\(t\)前\(i\)位，组内只有\(1\)个数\(x\),\(2\)个数为\(y\),\(3\)个数为\(z\),组内只有\(32\)个数为\(o\),组内只有\(13\)个数为\(p\),组内只有\(21\)个数为\(q\)。
结果为\(dp[3n][0][0][0][0][0][0]*n!\)
因为每一种\(n\)个组方案的其实是按最后一个元素的下标有序的。所以\(n\)个组，可打乱顺序，要乘\(n!\)。
转移就：组内已填大小：\(0-1/1->2/2->3\)
注意乘系数（可加入组的方案数），还有第一维\(3*n\)会暴要滚掉！
具体方程可见code.

code:

#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=20;
int n,dp[2][N][N][N][N][N][N];
char ch[N*3];
void DP(bool cur,bool lst,int opt) {
	if(opt==1) {
		for(int x=0;x<=n;x++) for(int y=0,up=n-x;y<=up;y++) for(int z=0,up=n-x-y;z<=up;z++) {
			for(int o=0,up=n-x-y-z;o<=up;o++) for(int p=0,up=n-x-y-z-o;p<=up;p++) for(int q=0,up=n-x-y-z-o-p;q<=up;q++) {
				if(x)dp[cur][x][y][z][o][p][q]=(dp[cur][x][y][z][o][p][q]+dp[lst][x-1][y][z][o][p][q])%mod;
				if(y