题解：CF1425B Blue and Red of Our Faculty!

· · 题解

::::info[前置知识：缺一分治] 考虑这样一个问题，01 背包，但是每次问你强制不选一个物品后的答案。考虑对这个不选的物品分治，每次处理不选物品在 [l,r] 时的答案，若 l=r，则我们直接用上一层预处理出的背包数组去更新答案。否则我们干这样的事情：

也就是说，我们干的事情是加一侧、递归另一侧。因此当 l=r 处理答案时，此时的背包恰好涵盖了 [1,l)\cup (l,n] 的物品。

分析下复杂度，每层递归做背包的物品个数是 O(r-l+1) 的，因此不难证明是 O(nV\log n) 的。 ::::

考虑下这个图张什么样，大概是中间有个 1 号点，然后和若干个环拼起来。刻画一下每个环最终可能会被染成什么样，发现我们有五种染色方式：

上图对应了这五种染色方式。

不妨考虑一下这五种染色方式是否真的都会存在。一个关键的性质是：用第三、四、五种染色方式的，至多有一个环。原因显然，因为当走到这些环内之后，移动必然会结束。

令 f_i 代表将每个环按照第一、二种方法染色，即全染或不染，目前蓝色边数与红色边数之差恰为 i 的方案数。转移显然，对于一个环长为 x 的环，可以选择不染、染成蓝的、染成红的，那么转移式为：

f'_i\leftarrow f_i+f_{i-x}+f_{i+x}

则我们要考虑的是去掉一个环之后剩下所有的环的 f_i。这是一个经典的缺一分治模型，直接做就好了。

当然这个题细节非常多，比如当 l=r 时具体应该怎么处理答案，以及如何区分第三、四、五种染色方案。对于 l=r 时，我们枚举这个环中有 i 条蓝边，此时环中可以有 0 条红边（第五种）、len-i 条红边（第三种）、len-i-1 条红边（第四种），我们需要分别加上其对应的状态。

特别注意，对于 0 条红边的情况，有些方案是不合法的，因为红方还可以继续往别的未染色（第二种）的环里走，因此我们可以再令 g_i 代表强制不用第二种染色方案的方案，特殊处理一下即可。

下面给出参考代码。

#include<bits/stdc++.h>
using namespace std;
const int N=4005;
const int M=15;
const int mod=1e9+7;
#define int long long
int n,m,cnt,tot,ans;
int a[N],vis[N],f[N][M],f2[N][M],tmp[N],tmp2[N];
//f[i]: cntblue-cntred=i
vector<int> g[N];
void dfs(int u){
    vis[u]=1,cnt++;
    for(auto v:g[u]){
        if(!vis[v]){
            dfs(v);
        }
    }
}
void solve(int l,int r,int dep){
    if(l==r){
        for(int i=1;i<a[l];i++){
            if(i==a[l]-1){
                ans=(ans+2*f[a[l]-i-i+n][dep])%mod;
            }else{
                ans=(ans+2*(f[a[l]-i-i+n][dep]+f[a[l]-i-i+n-1][dep]))%mod;
            }
        }
        return;
    }
    int mid=(l+r)/2;
    for(int i=0;i<=n*2;i++){
        f[i][dep+1]=f[i][dep];
    }
    for(int i=l;i<=mid;i++){
        for(int j=0;j<=n*2;j++){
            tmp[j]=f[j][dep+1];
            if(j+a[i]<=n*2){
                tmp[j]=(tmp[j]+f[j+a[i]][dep+1])%mod;
            }
            if(j-a[i]>=0){
                tmp[j]=(tmp[j]+f[j-a[i]][dep+1])%mod;
            }
        }
        for(int j=0;j<=n*2;j++){
            f[j][dep+1]=tmp[j];
        }
    }
    solve(mid+1,r,dep+1);
    for(int i=0;i<=n*2;i++){
        f[i][dep+1]=f[i][dep];
    }
    for(int i=mid+1;i<=r;i++){
        for(int j=0;j<=n*2;j++){
            tmp[j]=f[j][dep+1];
            if(j+a[i]<=n*2){
                tmp[j]=(tmp[j]+f[j+a[i]][dep+1])%mod;
            }
            if(j-a[i]>=0){
                tmp[j]=(tmp[j]+f[j-a[i]][dep+1])%mod;
            }
        }
        for(int j=0;j<=n*2;j++){
            f[j][dep+1]=tmp[j];
        }
    }   
    solve(l,mid,dep+1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    vis[1]=1;
    for(auto i:g[1]){
        if(!vis[i]){
            cnt=1,dfs(i),a[++tot]=cnt;
        }
    }
    f[n][0]=1;
    solve(1,tot,0);
    memset(f,0,sizeof(f));
    f[n][0]=1;
    for(int i=1;i<=tot;i++){
        for(int j=0;j<=n*2;j++){
            tmp[j]=tmp2[j]=0;
            if(j+a[i]<=n*2){
                tmp[j]=(tmp[j]+f[j+a[i]][0])%mod;
                tmp2[j]=(tmp2[j]+f2[j+a[i]][0])%mod;
            }
            if(j-a[i]>=0){
                tmp[j]=(tmp[j]+f[j-a[i]][0])%mod;
                tmp2[j]=(tmp2[j]+f2[j-a[i]][0])%mod;
            }
            if(j-(a[i]-1)>=0){
                tmp2[j]=(tmp2[j]+f[j-(a[i]-1)][0])%mod;
            }
            if(j+(a[i]-1)<=n*2){
                tmp2[j]=(tmp2[j]+f[j+(a[i]-1)][0])%mod;
            }
        }
        for(int j=0;j<=n*2;j++){
            f[j][0]=tmp[j];
            f2[j][0]=tmp2[j];
        }
    }
    cout<<(ans+f2[n][0]*2+f[n][0])%mod;
    return 0;
}