题解：CF1651E Sum of Matchings

· · 题解

提供一种比较好写的小常数做法。

注意到原图由若干偶环组成，容易想到对于每个环计算其贡献。设环长为 2n，贡献一定要么为包含整个环，贡献为 n；要么是若干条链，贡献为每条链点数整除 2 的值之和。

这里已经可以通过枚举链并确定链端点不取的方式直接精确计算每条链的贡献了，但是这样太麻烦了，有没有更简洁的做法呢？注意到确定链被包含比链恰好是极长的简单，这类问题我们都可以考虑容斥。

事实上，我们只要令一条长为 l(l>1) 链贡献为 (-1)^l，整个环贡献为 -n 即可，推导过程是平凡的。具体的，注意到 \lfloor\frac{l}{2}\rfloor=\displaystyle\sum_{i>1}(l-i+1)\times (-1)^i，而一个环被计算的贡献为 2n，令其权值为 -n 抵消多余贡献。

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define maxn 110005
typedef long long ll;
using namespace std;
const int inf=2e9+7;
int n,vis[maxn];
vector<int>e[maxn],vec;
void dfs(int x){
    vec.push_back(x);
    vis[x]=1;
    for(int i:e[x]) if(!vis[i]) dfs(i);
}
int main(){
    ll ans=0;
    scanf("%d",&n);
    for(int i=1,u,v;i<=n+n;i++) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
    for(int i=1;i<=n+n;i++){
        if(vis[i]) continue;
        vec.clear();
        dfs(i);
//      assert(vec.size()%2==0);
        int m=(vec.size()>>1);
        for(int i=0;i<m+m;i++){
            int min1=inf,max1=-inf,min2=inf,max2=-inf;
            for(int j=0;j<m+m-1;j++){
                int id=vec[(i+j)%(m+m)];
                if(id<=n) min1=min(min1,id),max1=max(max1,id);
                else min2=min(min2,id-n),max2=max(max2,id-n);
                if(!j) continue;
                ans+=(ll)(j&1?1:-1)*min1*(n-max1+1)*min2*(n-max2+1);
            }
            if(!i) ans-=(ll)m*min1*(n-max1+1)*min2*(n-max2+1);
        }
    }
    printf("%lld\n",ans);
}