五月杂题选做

s_r_f · 2020-05-08 15:02:11 · 个人记录

UOJ#286. 同构判定鸡

大概就是要构造出两个图,让他们不同构,并且让题目中给的6种同构的判法都判不出同构.

这里 有一种可行的构造,但是它怎么来的我就不知道了,强正则图是什么东西

因为这个网址太卡了,所以部分原文摘录如下:

可以发现，强正则图不管长啥样，只要参数固定了，它们的特征值就是固定的。

也就是说，一旦我们构造出了两个不同构的强正则图，就解决了这个问题。

事实上，这样的构造存在，且唯一。仅有当 $n = 4$ 时，存在两张不同构的图，均为 $srg \left( 16, 6, 2, 2 \right)$。它们分别是：

$K_4 \times K_4$，即完全图 $K_4$ 与其自身的 Cartesian 积：

Shrikhande graph，构造方法：令 $V = \left\{ 0, 1, 2, 3 \right\} \times \left\{ 0, 1, 2, 3 \right\}$，$S = \left\{ \left( 0, 1 \right), \left( 0, 3 \right), \left( 1, 0 \right), \left( 3, 0 \right), \left( 1, 1 \right), \left( 3, 3 \right) \right\}$，$E = \left\{ \left( (u_1, u_2), (v_1, v_2) \right) \mid \left( u_1, u_2 \right), \left( v_1, v_2 \right) \in V, \left( u_1 - v_1, u_2 - v_2 \right) \in S \right\}$。
以上运算均在环 $\mathbb Z_4$ 下进行。则图 $G = \left( V, E \right)$ 就是 Shrinkhande graph。

容易验证它们都是 $srg \left( 16, 6, 2, 2 \right)$。且它们的邻接矩阵的特征多项式为 $f \left( \lambda \right) = \left( \lambda - 6 \right) \left( \lambda - 2 \right)^6 \left( \lambda + 2 \right)^9$，特征值为一重的 $6$，$6$ 重的 $2$ 和 $9$ 重的 $-2$。
而它们的确是不同构的，因为 $K_4 \times K_4$ 显然有 $K_4$ 作为子图，然而 Shrinkhande graph 没有 $K_4$ 作为子图 (不用找了，真的没有)。

因此，我们只需将 $K_4 \times K_4$ 和 Shrinkhande graph 传给交互库，即可 Hack 掉所有 $6$ 种算法，而 identify() 的过程是非常容易的：只需判断是否有 $K_4$ 作为子图，爆搜即可。

CF582D Number of Binominal Coefficients

数位DP. 我的数位DP总结blog

考虑lucas定理的过程,设a = k,b = n-k,则在p进制下a+b有>=k次进位,且a+b<=A.

设dp[n][m][1/0][1/0]表示当前考虑到第n位, 还需要进位m次,这一位的数值是/否紧贴着上界,这一位是/否往上一位进位.

复杂度O(3500^2),其中3500为A在p进制下最大位数.

CF526F Pudding Monsters

把棋盘转成一个排列,然后一个区间合法的条件是max-min=r-l,

由于val =max-min-(r-l) \geq 0, 所以可以在线段树上记val的最小值以及最小值的出现次数即可.

单调栈+线段树维护.

[CERC2017]Intrinsic Interval

和上一题类似,一样的方法维护.

查询的时候,用一个set维护一下当前所有存在的询问,然后再写个线段树上二分的操作就可以查询了.

当然,这个题和上一个题都可以用析合树做,但是析合树太难写了.

P4318 完全平方数

首先这个不含平方因子的数满足μ(x)^2=1,并且有平方因子的数显然满足\mu(x)^2=0.

显然题目里面的第K大不容易直接求,考虑二分答案n

那么我们要check的就是

通过简单容斥可以发现

然后我们可以直接O(\sqrt n)暴力算出f(n).

考虑一种更优的做法:

不过由于n的数值不够大 并且此题可以分块打表, 所以这种做法的优越性并不能体现出来 . 所以有没有人出个N=10^{14},T=10^3的加强版啊 /kel

复杂度O(\sqrt N+TN^{1/3}logN).

还有一种O(N^{2/5})的算一次f(N)的做法.

就是筛O(N^{2/5})的\mu(i),然后剩余的\mu(i)前缀和杜教筛,再整除分块.

真的毒瘤

SP19148 INS14G - Kill them All

考虑把局面看成点,一开始在(0,0), Digo attack一次之后(x,y)->(x+1,y), Sharry attack 一次之后 (x,y)->(x,y+1).

然后我们可以发现,这个限制相当于第一步必须到(1,0),且接下来的每一步不能走到直线x=y上.

最终走到的终点就是(x,n-x),且x>n-x,即x\geq n-x+1,

每个x对答案的贡献是\large \binom{n-1}{x-1} - \binom{n-1}{x}.

最后发现式子之间会两两消去,最后的结果是 \large \binom{n-1}{ \lfloor \frac{n+1}{2} \rfloor -1}

然后预处理阶乘和阶乘逆元就做完了,复杂度O(N).

P6435 「EZEC-1」数列

记ans_n为第n行的第一项.

考虑第一项和第二项的差,它们一开始是1,然后每经过一行都会\times (a+b).

那么不难得到一个式子:

然后开始推式子:

记\large v_n = \frac{ans_n}{(a+b)^n}.两边除以 \large (a+b)^n:

由于p不一定是质数,所以最后的\large \sum\limits_{i=0}^{n-2} (a+b)^i 可以分治搞.

大概可以这么写:

inline LL qpow(LL x,LL y){
    x %= P; static LL r; r = 1;
    while (y){
        if (y&1) r = mul(r,x);
        x = mul(x,x),y>>=1;
    }
    return r;
}
inline LL F(LL a,LL n){
    if (n <= 1) return (n*a+1) % P;
    if (n&1) return mul((qpow(a,n+1>>1)+1) % P,F(a,n>>1));
    return (qpow(a,n) + mul((qpow(a,n>>1)+1) % P,F(a,n-1>>1))) % P;
}

然后就解决了.复杂度O(log^2),其中分治的部分如果改成倍增的话就可以做到O(log).

CF493D Vasya and Chess

以前在matrix67的一本书上看过类似的东西(((

大概是如果n是奇数,那么不论你怎么走,对方一定可以对称的复制你的操作,然后你就输了.

如果n是偶数的话,如果对方复制你的操作,最后必定会被你的棋子吃掉,所以你就赢了.

总结:这个题是一道猜结论好题但是在博弈论中有巨大的理论价值?

CF547D Mike and Fish

对于同一行/列的点,将两两配对之后连边,易证得到的图是二分图, dfs染色即可.

还有一种做法,就是考虑把(x,y)变成(x,y')即坐标和坐标之间连边,然后把度数为奇数的点和0连起来跑欧拉回路.

CF576D Flights for Regular Customers

但实际上并不需要这么繁琐,而且并不需要用到任何计算几何知识.

因为人被障碍挡住只可能是障碍覆盖了一条完整的从左/上到右/下的路径,所以直接O(N^2)跑个最短路就可以了.

而且这个题甚至可以用Dij+kdTree做到更优的复杂度.

[HEOI2013]Eden 的新背包问题

有两种思路:

一种是做前缀背包和后缀背包,每次询问O(e_i)枚举求答案,复杂度O(n*E*log(C)+q*E),其中E=\max\limits_{i=1}^{n}e_i,C=\max\limits_{i=1}^{n}c_i

或者可以写一个分治背包,复杂度O(n*E*log(C)*log(n)+q).

这两种做法一种瓶颈是n,一种瓶颈是q.

所以这个题是不是可以用一些其它的方法做到更平衡的复杂度啊?

P4256 公主の#19准备月考

观察题面,需要维护区间gcd和lcm.

值域是[1,100], [1,100]范围内的gcd可以事先预处理出来然后可以O(1)查询.

不难发现2^7=128>100,3^5=243>100,5^3=125>100,7^3=343>100,11^2=121>100

所以, 2 和 3 各自用 3 个二进制位 , 5 和 7 各用 2 个二进制位 , 剩下的 21 个质数各用 1 个二进制位 , 一共用 31 个二进制位 , 用一个 int 存正好能存下.

并且通过O(1024^2)预处理可以做到O(1)合并这个信息.

处理完这些信息之后,直接上线段树就好了. O(1024^2+nlogn)

my solution

P4388 付公主的矩形

不难发现N=R+C-\gcd(R,C),枚举 \gcd=d: n=r+c-1且[r \perp c]所以答案为: \sum\limits_{i|N}^{N} d(i+1)

水水水,再水这种简单题要完了啊

P6170 [USACO16FEB]Circular Barn G

大概是个贪心?就考虑破环为链,然后显然的就是按照顺序匹配.

做一个前缀min 可以 check 是否合法.

不过有一说一,一开始我写了一个O(n^2)暴力,加上最优性剪枝,竟然过题了……

到底是数据水还是卡不满啊(((

P6091 【模板】原根

补个板子.

然后check的时候显然不能O(nlogn)做,我们把φ(n)分解质因子之后只用check O(log)次了.

结合O(n)-O(1)\gcd的板子之后理论上可以做到O(n).

P5221 Product

推一波式子之后发现需要用到阶乘和\sum φ(i),然后发现这题卡空间.

所以阶乘的数组不能开,需要处理一下.

P6086 【模板】Prufer 序列

继续补板子.

做法没啥好说的.放个代码在这看看:

const int N = 5000005;
int n,fa[N],p[N],deg[N]; LL ans;
inline void work1(){
    register int i; int j;
    for (i = 1; i < n; ++i) rd(fa[i]),++deg[fa[i]];
    for (i = j = 1; i <= n-2; ++i,++j){
        while (deg[j]) ++j; p[i] = fa[j];
        while (i <= n-2 && !--deg[p[i]] && p[i] < j) p[i+1] = fa[p[i]],++i;
    }
    for (i = 1; i <= n-2; ++i) ans ^= 1ll * p[i] * i;
    cout << ans << '\n';
}
inline void work2(){
    register int i; int j;
    for (i = 1; i <= n-2; ++i) rd(p[i]),++deg[p[i]]; p[n-1] = n;
    for (i = j = 1; i <= n-1; ++i,++j){
        while (deg[j]) ++j; fa[j] = p[i];
        while (i <= n-1 && !--deg[p[i]] && p[i] < j) fa[p[i]] = p[i+1],++i;
    }
    for (i = 1; i <= n-1; ++i) ans ^= 1ll * fa[i] * i;
    cout << ans << '\n';
}
int main(){ int Tp; rd(n),rd(Tp); if (Tp == 1) work1(); else work2(); return 0; }

不知为何我交了这么多次还是\ 80 \ pts /yiw

P4243 [JSOI2009]等差数列

线段树在差分数组上维护dp.

开一个\ struct,封装重载好就可以维护了.

大概就是可以搞出递推式: ans_m =\sum\limits_{i=1}^{n} (-1)^{i+1 } \times ans_{m-i}a_i(m\geq n)

如果n比较大 ( 10^5 ) ,可以多项式求逆+线性递推解决.

P5299 [PKUWC2018]Slay the Spire

首先因为强化牌的数值一定>1,所以不难发现我们的策略一定是在保证至少打出一张攻击牌的时候尽量多的打出强化牌,然后根据这个策略dp即可.

P4281 [AHOI2008]紧急集合 / 聚会

练一下欧拉序+ st表求lca的板子.

大概就是答案一定在lca(x,y),lca(x,z),lca(y,z)当中.

注意写st表的时候把小的一维放到前面可以减少常数.

P2657 [SCOI2009] windy 数

Link:我的数位DP总结Blog

数位dp,状态记录一下上一位即可.

P2455 [SDOI2006]线性方程组

补板子,顺便复习下高斯消元.

这个题需要我们check有解/有无穷多解/无解

注意交换行的时候可能需要和上面的某一行交换,比如说这个case:

2
0 1 1
0 0 0

如果在消元的时候没有交换,会被判成-1.

const int N = 55;
int n; db A[N][N];
int main(){
    int i,j,k; db v;
    cin >> n;
    for (i = 1; i <= n; ++i) for (j = 1; j <= n+1; ++j) cin >> A[i][j];
    for (i = 1; i <= n; ++i){
        if (fabs(A[i][i]) < eps){
            for (j = 1; j <= n; ++j) if (j != i && (j > i || fabs(A[j][j]) < eps) && fabs(A[j][i]) > eps){
                for (k = 1; k <= n+1; ++k) swap(A[i][k],A[j][k]); break;
            }           
        }
        if (fabs(A[i][i]) > eps){
            for (j = 1; j <= n; ++j) if (j != i && fabs(A[j][i]) > eps){
                v = A[j][i] / A[i][i];
                for (k = 1; k <= n+1; ++k) A[j][k] -= A[i][k] * v;
            }
        }
    }
    for (i = 1; i <= n; ++i){
        if (fabs(A[i][i]) < eps && fabs(A[i][n+1]) > eps){ puts("-1"); return 0; }
    }
    for (i = 1; i <= n; ++i){
        if (fabs(A[i][i]) < eps && fabs(A[i][n+1]) < eps){ puts("0"); return 0; }
    }
    for (i = 1; i <= n; ++i){
        v = A[i][n+1] / A[i][i];
        printf("x%d=%.2lf\n",i,v);
    }
    return 0;
}

P5656 【模板】二元一次不定方程(exgcd)

继续补板子.

感觉这个板子的难点好像在exgcd之后的部分啊(

细节还好,不算多,就是有点烦(((

就直接CRT,需要写exgcd求逆元.

#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
    if (!b) d = a,x = 1,y = 0;
    else exgcd(b,a%b,d,y,x),y -= (a/b) * x; 
}
inline LL Inv(LL a,LL P){
    static LL d,x,y; a %= P; exgcd(a,P,d,x,y);
    return d == 1 ? (x%P+P)%P : -1;
}
inline LL mul(LL a,LL b,LL p){
    static LL an; an = a*b - (LL)((long double)a*b/p) * p;
    if (an >= p) an -= p; else if (an < 0) an += p; return an;
}
int n;
inline LL calc(int n,LL *a,LL *b){ //X % b[i] == a[i]
    int i;
    LL m = 1,ret = 0;
    for (i = 1; i <= n; ++i) m *= b[i];
    for (i = 1; i <= n; ++i) ret = (ret + mul(a[i],mul(Inv(m/b[i],b[i]),m/b[i],m),m)) % m;
    return ret;
}
LL r[15],m[15];
int main(){
    cin >> n; for (int i = 1; i <= n; ++i) cin >> m[i] >> r[i];
    cout << calc(n,r,m) << '\n';
    return 0;
}
/*
input:
2
1000000009 444444 
998244353 33412312 
output:
19393407174985107
*/

P3301 [SDOI2013]方程

继续补板子.

显然这个题可以容斥一下,然后变成O(T\times 2^{n1})次查询组合数.

然后因为模数非质数,写个扩展卢卡斯就可以了.

所以这题被我当成了扩展卢卡斯模板题(大雾

CF1344D Résumé Review

补CF.

就考虑拉格朗日乘数法的式子.

对b_i求偏导得 λ=a_i-3b_i^2

然后考虑二分λ,但是因为有b_i\leq a_i 的限制,所以我们算出来的b_i可能不合法.

不过不合法的部分排序后显然是连续的一段,在外层再套一层二分即可.

然后求得了实数解,求整数解就是先令所有b_i=\lfloor b_i \rfloor 然后再排序贪心.

CF512D Fox And Travelling

首先找出所有可能被访问到的点,不难发现它们构成了一个森林.

如果一棵树和不可能访问到的点不相邻,就枚举根做O(size)次DP,最后把对应的方案数cnt_i->cnt_i /(size-i), ( 因为它被计算了(size-i)次 )

否则根一定是那个和不可能访问到的点相邻已经固定,直接DP.

树和树之间的合并直接乘组合数就可以了.

CF986C AND Graph

建O(2^n)个辅助点i'表示i'连向所有是i'子集的点, dfs即可.

CF1349D Slime and Biscuits

补CF. xtq Round, Best Round!

这里是xtq的官方题解

式子没啥好说的,里面都有.

我的实现方法是把f_0设成未知数然后递推到f_m,用方程f_m=0解出所有的f.

复杂度为 O(n+\sum a_i) 或者 O((n+\sum a_i)logP)

不懂为啥有些代码里要求O(n)次快速幂/yun

CF1000F One Occurrence

是在莫队题单里看到的,然而这个题可以用数据结构O(nlogn)做.

为了补板子,所以我把它当成了可持久化线段树练习题(((

考虑一个位置i在询问(l,r)下合法的条件:

然后按nxt_i一维建可持久化线段树,然后在线段树上维护pre_i的最小值即可.

这个题也可以离线,做法差不多.

一个思路类似但更简单的题(只需要BIT): SP3267 DQUERY - D-query

CF940F Machine Learning

带修莫队板子题.

P5906 【模板】回滚莫队&不删除莫队

回滚莫队板子题.这个题大概是包括了只加不减的回滚莫队的通用情况的板子.

这里推荐一个回滚莫队的讲解,包含了只加不减和只减不加这两种情况.

首先分块,一个块内的询问暴力扫,然后跨越块的询问一起处理.

把同一块的询问按r从小到大排序,然后一边移动r一边O(S)回答一次关于l的询问.

代码大概像这样:

const int N = 200005;

int v[N],lv;
int n,m,a[N],cur[N],ans[N];

int vl[N],vr[N],now;//当前的数组
int cvl[N],cvr[N],cnow;//用于保存信息的数组
inline void Init(){//初始化/清零
    memset(vl,0,lv+1<<2),memset(vr,0,lv+1<<2),now = 0;
}
inline void Add(int x,int p){//加入一个点
    if (!vl[x]) vl[x] = vr[x] = p;
    else vl[x] = min(vl[x],p),vr[x] = max(vr[x],p);
    now = max(now,vr[x]-vl[x]); 
}
inline void Save(int l,int r){//保存信息
    for (int i = l; i <= r; ++i) cvl[a[i]] = vl[a[i]],cvr[a[i]] = vr[a[i]]; cnow = now;
}
inline void Copy(int l,int r){//还原信息
    for (int i = l; i <= r; ++i) vl[a[i]] = cvl[a[i]],vr[a[i]] = cvr[a[i]]; now = cnow;
}

int csiz;
struct Ask{
    int id,l,r;
    bool operator < (const Ask w) const{ return cur[l] != cur[w.l] ? l < w.l : r < w.r; }
}ask[N]; int q;
int main(){
    int i,j,l,r;
    read(n);
    for (i = 1; i <= n; ++i) read(a[i]),v[i] = a[i];
    sort(v+1,v+n+1),lv = unique(v+1,v+n+1) - v - 1;
    for (i = 1; i <= n; ++i) a[i] = lower_bound(v+1,v+lv+1,a[i])-v-1;
    read(m),csiz = m/(1+sqrt(n))+1;
    for (i = 1; i <= n; ++i) cur[i] = (i-1)/csiz+1;
    for (i = 1; i <= m; ++i){
        read(l),read(r);
        if (cur[l] == cur[r]){
            for (j = l; j <= r; ++j) Add(a[j],j);
            ans[i] = now;
            Copy(l,r);
        }
        else{
            ++q; ask[q].id = i,ask[q].l = l,ask[q].r = r;
        }
    }
    sort(ask+1,ask+q+1);
    for (i = j = 1; i <= cur[n] && j <= q; ++i){
        if (cur[ask[j].l] != i) continue;
        Init(),l = r = i * csiz + 1,Add(a[l],l);
        while (j <= q && cur[ask[j].l] == i){
            while (r < ask[j].r) ++r,Add(a[r],r);
            Save(ask[j].l,l-1);
            while (l > ask[j].l) --l,Add(a[l],l);
            ans[ask[j].id] = now;
            l = i * csiz + 1;
            Copy(ask[j].l,l-1);
            ++j;
        }
    }
    for (i = 1; i <= m; ++i) write(ans[i]),putchar('\n');
    return 0;
}

SP744 LPERMUT - Longest Permutation

考虑一个区间合法的条件为:区间必须有1,区间不能有重复的数值,区间的和为\frac{mx\times(mx+1)}{2}.

然后考对于每一个1都做一遍,枚举右端点,假设max在右边,然后就可以直接算出区间的L,然后利用前缀和可以O(1)check sum是否符合条件.

然后区间不能有重复的数值,就莫队移动左端点,可以证明在加上适量剪枝的情况下移动左端点总次数为O(n)

最后我们把区间翻转一下再做一遍就能解决max在左边的情况了.

CF1198F GCD Groups 2

首先先把所有a_i的质因子次数>1的变成1次 ,这个可以用Pollardrho做,也可以只去除一些小的质因子p的平方因子以保证效率.

每次random shuffle一下然后直接贪心做.

先把a_1放进集合1,对于集合1我们只考虑能使其gcd的变小的,其余的都扔进集合2里.

可以发现随机了足够多次之后错误率会很低.

具体的正确性?

考虑整个贪心的过程,它确定了一个数字{a_1}作为初始的S_1的元素,那么具体的方案就是a_1加一些可以使gcd(S_1,v)变小的数字v.作为S_1.

不难发现v最多只会有log个,并且其它的数都会到S_2里去.

然后感觉一下这样得到答案的概率貌似挺高的?

然后对于S_2来说我们可以设第一个选了S_2的变量是a_w,然后也最多只有O(log)个会有贡献.

编不下去了,不会证,溜了溜了

SP10707 COT2 - Count on a tree II

树上莫队板子题.

AT1219 歴史の研究

只加不减的回滚莫队题.

但是AT的 remote judge 好像出锅了,所以被迫到AT上交.(((

P1758 [NOI2009]管道取珠

考虑题目中给的式子要你求的是什么.

也就是枚举两种方案A和B,这两种方案得到的结果序列相同.

然后就可以dp啦!

记dp_{t,i,j}表示操作t次，方案A上管道取到了i,方案B上管道取到了j

然后滚动数组就解决了.

P3802 小魔女帕琪

简单题.

不难发现在任意位置发生帕琪七重奏的概率是相等的,于是直接计算概率即可.

AGC044D Guess the Password

交互题.

考虑令f(S)表示包含了字符集S中的所有字符的答案串中的子序列.

首先我们可以通过10+26+26=62次询问得到f('a'),f('b')...

然后考虑合并两个f(s)和f(t),最多需要|f(s)|+|f(t)|次询问.

每次合并两个小的即可.

最多操作次数769.

CF639E Bear and Paradox

被搬到了某校内模拟赛T1.

首先考虑怎么求出最优的方案.

不难发现如果\large \frac{a_i}{t_i}> \frac{a_j}{t_j},那么i必然在j之前.

那么我们就可以求出,对于每一个题目,它的最早完成时间和最晚完成时间.

接下来我们考虑那个限制.

如果 \large a_i<a_j,那么 \large b_i<b_j

接下来如果 (a_jx_j-a_ix_i)<0,那么这个限制就没用( 形如c>一个负数 )

否则可以解出

然后我们已经求出了所有x_i的最大/最小值,因此这个限制可以直接计算.

然后这个题就可以解决了.

根据实现的不同复杂度为O(nlogn)或O(nlogANS).

P5572 [CmdOI2019]简单的数论题

莫比乌斯反演.

复杂度是O(TN^{3/4})的,然后写法需要注意一些东西需要预处理.

我实现的很丑,需要卡常.

P6178 【模板】Matrix-Tree 定理

补板子.

AGC044E - Random Pawn

首先不难发现,如果我们走到了环上A_i最大的点,那么就可以直接停下来了,所以根据这个我们可以发现环的问题被转化成了数列问题.

有E_i=max(A_i,\frac{E_{i+1}+E{i-1}}{2}-B_i),但是这个显然无法计算.

令策略为对于∈[L,R]的位置p,如果走到了L或R就停下,否则一直花费B_p的钱移动.

那么不难得到E_L=A_L,E_R=A_R 对于i∈(L,R),E_i=\frac{E_{i+1}+E{i-1}}{2}-B_i

令E_i的差分d_i为E_i-E_{i-1},不难发现对于有意义的i(∈(L,R]), d_{i+1}=d_i+2B_i

因此,通过维护B_i和i\times B_i

可以在O(1)时间内回答关于区间[L,R]如果策略为 \qquad "走到了L或R就停下,否则一直花费B_p的钱移动" \qquad 在某个点的E_p的值.

然后不难发现策略一定是有若干个点,走到这些点就停下,其他点继续移动.

这个直接用栈贪心一下就好了. 复杂度O(n).

评测链接:Link

P6583 回首过去

随便反演可以得到80分

然后发现可以O(\sqrt n)预处理,所以就没了.

CF739E Gosha is hunting

一开始怎么写都过不去,然后二分范围从[-1,1]改成[-2,2]就过了.

P3690 【模板】Link Cut Tree （动态树）

最简单的LCT板子.

第三个要写min25筛,先鸽着.

AGC028D - Chords

又被搬到了模拟赛T1.

考虑一个联通块对答案的贡献.

记G[n]表示一个大小为n的集合内部两两匹配的方案数.

不难发现G[n] = fac[n] * nfac[n/2] * \frac{1}{2^{\frac{n}{2}}}.

然后记F_{l,r}表示区间[l,r]内部和外部不连边, l与r相邻的方案数.

转移的时候考虑容斥,即枚举与l联通的最右的点,然后容斥掉这种情况.

总方案数可以用G[i]来算.

BZOJ2407

考虑枚举第一条边,然后次短路,没了(

不过有点难写.