rank 29 mark 150
题纲：T1：赛时全员AC，其他的应该不用说什么了
T2：图论，竞赛图统计强连通分量（位运算的应用）
T3：计数类DP
T4：线段树维护dfs序-->树剖-->染色
T2:定义竞赛图，任意两点之间都有且只有一条有向边。给你一个竞赛图n个节点，求强连通子图数量。n<=27
状压方法：就像线性筛一样，我在从“1”状态更新到“2^n-1”状态的时候，用当前合法状态更新到以后的不合法状态，标记上，这样我从小到大每次循环到的的
当前状态就一定合法性已知（就像质数一样）。mp[x]记录当前x包含的点集可以到哪些点，因为竞赛图，所以x里每个点都可以到达的点一定无法回去，这样只
要包含一个这样的点的状态一定都是不合法的，【奇妙的方法】用j记录mp[x]的值，每次-1然后&x,就可以循环完所有mp[i]里包含的“1”的状态。用合法方案
减去筛到的不合法的就是答案。（在记录mp的时候，可以直接用最低位的“1”和去掉之后的&上更新答案，因为去掉“1”之后，本来就是从小到大更新，去掉之后
的一定更新过了，单点就是继承原来的状态）.
O(2^n)
T3:3个小朋友分糖果，每个人对糖果都有一个喜好程度的排列，糖果本身是一个排列，每一轮3个人同时拿自己最喜欢的还没拿的糖果。已知1号和2号的喜好排列，求3号的合法（每个人拿完所有糖果，不存在一轮里某两个人要拿同一个糖果的情况）喜好程度方案数量(n<=400)
暴力搜索c的排列-->发现只要c的拿到糖果序列确定，可以通过排列算出c的决策序列。假如c的抉择序列是U，那么，不在c的抉择序列里的n/32个数也要塞到c里面。考虑怎么塞合法，就是对于c中在posi位置出现的非抉择ci，在a和b中一定要在posi之前出现（a，b都是拿到糖果序列）。所以对于在c(n/3)位置，b(n/3)只有1个位置就是在c(n/3)后面（否则这个数就c选了），a(n/3)也是，只不过因为b进去了，就有了2个空隙，b有2种选择。当b(n/3-1)个位置，就有c(n/3-1)~c(n/3)的区间范围都可以选，也就是倒着插孔空可以构造除正着不好构造出的序列，所以ans=\(\prod\)(3i-1)*(3i-2) (1<=i<=n/3)
https://www.cnblogs.com/TYubai/p/15236580.html
const ll mod=1e9+7;
const int N=410;
int n,a[N],b[N],pa[N],pb[N];
ll dp[N][N][152][2];
int main()
{
// freopen("c.in","r",stdin);
// freopen("","w",stdout);
n=re();
_f(i,1,n)a[i]=re(),pa[a[i]]=i;
_f(i,1,n)b[i]=re(),pb[b[i]]=i;
dp[1][1][0][0]=1;//就是说A要选还没选呢，只有1种方案
ll ans=0;
_f(i,1,n+1)
_f(j,1,n+1)
_f(k,0,n/3)
{
dp[i][j][k][0]%=mod;
dp[i][j][k][1]%=mod;
if(i==n+1&&k==0)
{
ans+=dp[i][j][k][0];ans%=mod;continue;
}
if(dp[i][j][k][0])
{
if(pb[a[i]]<j)dp[i+1][j][k][0]+=dp[i][j][k][0];//b
else
{
dp[i][j][k][1]+=dp[i][j][k][0];//a nxt b
if(k>0)dp[i+1][j][k-1][0]+=dp[i][j][k][0]*k;//c,still a
}
}
if(dp[i][j][k][1])
{
if(pa[b[j]]<i)dp[i][j+1][k][1]+=dp[i][j][k][1];
else if(a[i]!=b[j])
{
dp[i+1][j+1][k+1][0]+=dp[i][j][k][1];
//这是本轮结束了，所以i+1，j+1，但是上面的本轮还没结束（b还没选完呢）
//如果b选了，下一个该c选但是不知道c要选什么，所以下一个a
if(k>0)dp[i][j+1][k-1][1]+=dp[i][j][k][1]*k;
}
}
}
_f(i,1,n)
{
if(i%3)ans=ans*i%mod;
}
//这里的理解就是，假如给定了C每次选择的糖果（中间跳过了哪些不知道）
//的序列
chu("%lld",ans);
return 0;
}