JZOJ 7066. 【2021.4.24 NOI模拟】ehzeux与圆周
题目大意
圆周上有 2 ∗ n 2*n 2∗n个点，两两相连构成 n n n个点对，其中有 m m m个点对已经连好，求所有方案下的连通块数量和。当两个点相连或所在线段相交则称之为属于同一个连通块。 n , m ≤ 300 n,mle300 n,m≤300题解
需要发现一个性质，把圆周展开成一条线段后和原来是一样的，并不会影响线段的连通。考虑把每种情况的连通块数量总和，转化为每个连通块出现的次数总和。设 f i , j f_{i,j} fi,j为 [ i , j ] [i,j] [i,j]为一个连通块时区间内不同连边的方案数，且 [ i , j ] [i,j] [i,j]外连边的点有 x x x个，则对答案的总贡献为 f i , j ∗ x ! 2 i 2 ( i / 2 ) ! f_{i,j}*frac{x!}{2^{frac{i}{2}}(i/2)!} fi,j∗22i(i/2)!x!，设后面的系数为 g x g_x gx，含义为把所有数全排列后相邻的两两连边，去掉每对顺序可以交换，且不同对之间顺序可以打乱的方案数。转移只需用一个区间内各种连边的总数减去不合法的方案数，即用当前区间内各种连边总方案减去 [ i , l ] ( l ∈ ( i , j ) ) [i,l](lin(i,j)) [i,l](l∈(i,j))作为一个完整连通块的方案数。记得若 [ i , j ] [i,j] [i,j]中有向外连的边，则 f i , j = 0 f_{i,j}=0 fi,j=0。代码
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 310 #define ll long long #define md 1000000007 struct {int x, y; }a[N]; ll f[N * 2][N * 2], g[N * 2]; int si[N * 2], p[N * 2][N * 2]; int main() {int n, m, i, j, k, l;ll ans = 0;scanf("%d%d", &n, &m);n *= 2;for(i = 1; i <= m; i++) {scanf("%d%d", &a[i].x, &a[i].y);si[a[i].x] = si[a[i].y] = 1;p[a[i].x][a[i].y] = p[a[i].y][a[i].x] = 1;}for(i = 1; i <= n; i++) si[i] = si[i - 1] + (si[i] == 0);for(i = 0; i <= n; i++) if(i % 2 == 0) {g[i] = 1;int t = i / 2;for(j = i / 2 + 1; j <= i; j++) {g[i] = g[i] * j;while(t && g[i] % 2 == 0) g[i] /= 2, t--;g[i] %= md;}}for(k = 1; k <= n; k++) if(k % 2 == 0) {for(i = 1; i + k - 1 <= n; i++) {j = i + k - 1;f[i][j] = g[si[j] - si[i - 1]];for(l = i + 1; l < j; l++) {f[i][j] = (f[i][j] - f[i][l] * g[si[j] - si[l]] % md + md) % md;}for(l = 1; l <= m && f[i][j]; l++) {if((a[l].x >= i && a[l].x <= j) != (a[l].y >= i && a[l].y <= j)) f[i][j] = 0;}(ans += f[i][j] * g[si[i - 1] + si[n] - si[j]] % md) %= md;}}printf("%lldn", ans);return 0; }
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
