9.28 daimayuan 模拟赛总结

感觉 -S 模拟赛时间好紧啊

复盘

8:00 开题

扫了一遍四道题，感觉 T1 很典，T2 有点神秘，T3 计数，但限制是简单的，看上去非常可做；T4 也有点神秘

推 T1，先定根，然后树形dp是显然的，这样有 $n^2$ 了，然后一般套路就是接下来推怎么换根…下意识觉得换根细节可能会比较多，决定先推一下别的性质

然后就突然蒙出来一个结论：当 $ans\geq 2$ 时，路径必定经过重心，跑一次 $O (n)$ dp 就行了

想了想怎么证明，发现考虑一个类似点分治的过程，第一次选出全局重心是不会比后面差的，所以应该是对的

8:50 过了大样例，然后突然想到没有处理 $an s = 1$ 的情况，想了一会，大概 9:10 写完交了

然后又磨了一会，手玩了几组样例，越发觉得这个结论是对的。

感觉花的时间有点长了，决定开下一道题已经 9:30 了

决定先推 T3，每一步思路都很顺畅，最后走到环上独立集，需要背包合并，表面看是 $n^3$ ，实际分析一下发现和树上背包一样是 $n^2$ 的，于是开写

10:30 写完了，样例没过，调到 10:50 过了大样例

赶紧开 T2 ，发现其实和以前见过的某道题很像，直接二分求就行了，然后潜意识认为和之前那道题一模一样，求 $[l, r]$ 元素的和

细节不少，看了眼时间不是很多，有点急

终于写完，已经 11:40，准备测样例看到是输出每个元素的值？才发现看错题了

简单想了想感觉最后那部分有点细节，不太好做，一时间决定打个暴力就润了

然后就结束了

结果是

65 + 35 + 100 + 0 = 200 , rk $O (n!)$

T1 以为是结论假了，最后经提醒发现是多测没清空！唉
其实如果往换根的方向想一想就可以得到一个正确性完全有保证且细节少的做法，不用浪费那么久的…
T2 最后就差一步了，那个东西可以直接暴力枚举所有元素的，时间太紧没想清楚
T4 应该看看的，没想象中的那么不可做

题解

T3

在这里插入图片描述

看到错排，反着来显然更好做，直接考虑容斥：钦定 $c$ 中 $x$ 个位置填的数与 $a$ 或 $b$ 相等，剩下随便。设钦定的方案数为 $g_x$ ，那么答案可以表示为 $\sum_{x=0}^n (-1)^xg_x(n-x)!$

考虑怎么求 $g_x$ ，朴素的想法是枚举在 $a$ 中钦定 $A$ 个位置， $b$ 中 $x - A$ 个，方案数为 $\sum\Large(^n_A)(^{n-A}_{x-A})$

手画一下发现这样会算到一些不合法的，举个例子：

在这里插入图片描述

如果我在 $a$ 中选出了 $2, 3$ 两个数，接下来又再 $b$ 中选出 $2$ 这个数，那么对于 $2$ 这个数字来说，不可能 $c_4,c_6$ 同时等于 $2$ ，所以这是一种不合法的钦定

考虑对这个再进行一次容斥：从 $1\sim n$ 种数中选出 $s$ 种数，钦定这些数在 $a$ 和 $b$ 中都被选出来了，设该方案数为 $h_s$

用 $h_s$ 来求 $g_x$ ，已经选出了 $s$ 种数，也就是钦定了 $2 s$ 个位置，剩下需要再钦定 $x - 2 s$ 个位置，直接组合数

$g_x=\sum_{s=0}^x (-1)^sh_s\large(^{n-2s}_{x-2s})\sum_{i=0}(^{x-2s}_i)$

最后的求和含义是把选出的位置分配到 $a$ 和 $b$ 中，显然是组合数一行的和

考虑求 $h_s$ ，发现这个选数不能随便组合数，因为可能同一个位置的上下两个数都被选到，如上图， $2$ 和 $3$ 是不能同时被钦定的 (在位置4产生了冲突)

我们分析一下这个限制的本质是什么：建出代表 $1\sim n$ 的 $n$ 个点，对每个位置的上下两个数连边，有边直接相连的两种数不能被同时钦定

容易发现这样形成的必定是若干个环，每个环是独立的，求出单个环的方案后分组背包合并一下即可求出整个的方案

n 元环 k 元独立集计数

对于一个环，设 $f_{len,x}$ 表示长 $l e n$ 的环中选出 $x$ 个不相邻的点的方案，枚举 $1$ 号点是否被选择即可破环成链

链上选出若干个不相邻的点就很好做啦

#include<bits/stdc++.h>
using namespace std ;typedef long long LL ;
const int N = 1010 , mod = 1e9+7 ;int n , a[N] , b[N] ;
LL l[N][N] , C[N][N] , fac[N] , Pw[N] ;
int tmp[N] , len , pos[N] ;//环 
bool vis[N] ;
LL dp[N] ;//考虑前i个环，一共选了x个 
inline LL V( int len , int x )
{if( len <= 3 ) {if( x == 0 ) {return 1 ;}if( x == 1 ) {return len ;}return 0 ;}return (l[len-1][x]+l[len-3][x-1])%mod ;//x!=0
}
inline LL pw( int x )
{if( x&1 ) return -1 ;return 1 ;
}
void solve()
{scanf("%d" , &n ) ;for(int i = 1 ; i <= n ; i ++ ) {scanf("%d" , &a[i] ) ;pos[a[i]] = i ;vis[i] = 0 ;}for(int i = 1 ; i <= n ; i ++ ) {scanf("%d" , &b[i] ) ;}len = 0 ;for(int i = 1 ; i <= n ; i ++ ) {if( vis[i] ) continue ;int now = i , cnt = 0 ;while( 1 ) {if( vis[now] ) break ;vis[now] = 1 ;cnt ++ ;now = pos[b[now]] ;}tmp[++len] = cnt ;}int sum = 0 ;for(int i = 0 ; i <= n ; i ++ ) dp[i] = 0 ;dp[0] = 1 ;for(int i = 1 ; i <= len ; i ++ ) {for(int j = sum ; j >= 0 ; j -- ) {for(int k = tmp[i]/2 ; k >= 1 ; k -- ) {dp[j+k] = ( dp[j+k] + dp[j]*V(tmp[i],k) ) % mod ;}}sum += tmp[i] ;}LL ans = 0 ;for(int x = 0 ; x <= n ; x ++ ) {LL g = 0 ;for(int s = 0 ; s <= x && 2*s<=x ; s ++ ) {g = ( g + pw(s)*dp[s]*C[n-2*s][x-2*s]%mod*Pw[x-2*s] ) % mod ;}ans = ( ans + pw(x)*g*fac[n-x] ) % mod ;}printf("%lld\n" , (ans+mod)%mod ) ;
}
void pre_work( int n )
{for(int i = 0 ; i <= n ; i ++ ) {C[i][0] = 1 ;for(int j = 1 ; j <= i ; j ++ ) {C[i][j] = ( C[i-1][j] + C[i-1][j-1] ) % mod ;}}l[0][0] = 1 ; fac[0] = 1 ; Pw[0] = 1 ;for(int i = 1 ; i <= n ; i ++ ) {fac[i] = fac[i-1] * i % mod ;Pw[i] = Pw[i-1] * 2 % mod ; for(int j = 0 ; j <= i ; j ++ ) {if( i == 1 && j == 1 ) l[i][j] = 1 ;else l[i][j] = ( l[i-1][j] + ((i>=2&&j>=1)?l[i-2][j-1]:0) ) % mod ;//链独立集}}
}int main()
{pre_work(1001) ;int t ;scanf("%d" , &t ) ;while( t -- ) solve() ;return 0 ;
}