T9 Kuro and Topological Parity (CF979E)

· · 个人记录

T9 Kuro and Topological Parity (CF979E)

CF传送门

洛谷传送门

题意简述

给定 n 个点，每个点有黑白两种颜色（如果没有颜色，那么你可以把它任意涂成黑色或白色），同时你可以在这个图上任意加入一些边（当然不能加入重边或自环），要求加入的边必须从编号小的点指向编号大的点。

我们称一条好的路径为经过的点为黑白相间的路径，如果一个图好的路径的总数 % 2= p ，那么我们称这个图为好的图，现在给定你 n 个点的情况，求这 n 个点能组成的好的图的个数，答案取模 1e9+7

数据范围
1 \leq n \leq 50$ $ (ex: 1 \leq n \leq 1e6) 0 \leq p \leq 1
题解

这是 O(n) 的题解

这题在理解上有很多岔路，所以我会标出容易误解的地方

为了方便，“好的路径”基本都会用“路径”来代替

题意

解释一下，黑白相间指的是黑连向白，白连向黑

比如 1 \rightarrow 0 \rightarrow 1，0 \rightarrow 1 \rightarrow 0 \rightarrow 1，1

思路

首先第一眼，是跟奇偶性相关的计数问题

所以重心就落在了奇偶性上

然后发现加入的边必须从编号小的点指向编号大的点

显然是无环的，而且拓扑序就是顺序

直接dp好了

然而点也要选，边也要选，可能性太多了qwq

那我们先不要管点，只考虑连边

既然是按点dp，不妨来设想加入一个点，让前面的点向它连边

可是随机性太大了啊，所以要加状态来限制

首先能想到的就是颜色，要么是黑，要么是白

但这还不够。因为我们想统计的是路径数的奇偶性，而黑或白根本没有体现

所以还要再加上两种状态：连到这个点的路径总条数，要么是奇，要么是偶

综合起来，就是四种状态

+ 这四个是状态，不是点的属性！不是把点分为这四类，而是**统计一个点有这些状态时的方案数** + 奇偶性指的是好的路径的**总条数**，而不是长度！ + 一个点不是只能被一个前面的路径连上，可以**任意连**！（甚至可以不连）而这些都加进方案数里，我们要做的就是区分这些方案的奇偶性 那我们就来区分这些方案的奇偶性吧 假设我新的 $i$ 号点是白色的，它已经连向了一些点了（或者没有连） 考虑它再连向先前的另外**一个点**，显然需要分情况讨论 + 如果这个点是也白色的，那连向它也不会被算进好的路径里，**不管连不连都不影响奇偶性** + 如果这个点是偶黑，连向它方案数等于加了一个偶数，**不管连不连都不影响奇偶性** + 如果这个点是奇黑？ + 这个时候不能再单独考虑了，需要结合整体考虑 + 如果 $i$ 号点一共连向了奇数个奇黑，那**奇偶性会改变**（奇 $\times$ 奇 $=$ 奇） + 如果 $i$ 号点一共了连向了偶数个奇黑，那**奇偶性就不会改变**（奇 $\times$ 偶 $=$ 偶） 总结一下，**如果不考虑奇黑，不管怎么连都不会改变奇偶性**，所以可以随意连 那如果考虑奇黑？ 其实有个很巧妙的想法，**可以拿出一个奇黑来控制奇偶性** 这个奇黑是可以选择连或不连的，而这两种情况奇偶性肯定不相同 > 举个例子，比如其它 $i-2$ 个点已经连好，路径总数是奇条 > 如果果不连这个奇黑，奇的方案++ > 如果连这个奇黑，偶的方案++ 好，那么奇或偶的方案数就是各加上 $2^{i-2}$种 （因为选出一个奇黑控制奇偶性，其它随便选，选或不选） 噢，我们还漏了一种情况 如果一个奇黑都没有呢？ 那奇偶性根本就改变不了了，只能是它自己一个点不连边，奇的方案总数…… 那它也就只能做奇白了，方案数加上 $2^{i-1}$ 种 （不用选出一个奇黑控制奇偶性了，随便选） 那 $i$ 号点是黑的情况也能同理可得了 思路大概就是这样了，或许不是很清晰？慢慢理解吧 **做法** ~~这才是精髓啊~~ 根据上面的解释，dp数组的值肯定是方案数 但状态呢？ 再看一眼总结，会发现我们只关心**有没有奇黑（或奇白）** 而其它的都很巧妙地被奇偶性绕开了 **存状态就只存这个！** 设 $f[i][id][ob][ow]$ 为**前i个点**里，路径总条数的奇偶性是偶或奇，有无奇黑，有无奇白的**方案总数** 而 $O(n)$ 是怎么做到的呢？ **每次只转移上一个** 这也是为什么状态设计的是前 $i$ 个点里的总和，而不仅仅是第 $i$ 个点 这样转移状态的时候就不仅仅是 $2^{i-1}$ 或 $2^{i-2}$ 次方了，还要**乘**上 $f[i-1][][][]

为什么呢？

因为 f[i-1][][][] 意思是不包含 i 号点的方案数

而转移计算的是包含 i 号点的方案数

两种情况互不干扰，可以理解成先选不包含 i ，再选包含 i ，乘法原理

答案直接统计 f[n][p][][] 即可

O(n)

注意事项

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1000000+5,mod=1e9+7;
long long n,p;
long long a[N],fx[N],f[N][2][2][2];
int main(){
    scanf("%lld%lld",&n,&p);
    for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
    fx[0]=1;
    for(long long i=1;i<=n;i++) fx[i]=fx[i-1]*2%mod;//预处理2^i 
    f[0][0][0][0]=1;//初始化 
    for(long long i=1;i<=n;i++)//枚举i 
        for(long long id=0;id<=1;id++)//枚举id
            for(long long ob=0;ob<=1;ob++)//枚举ob
                for(long long ow=0;ow<=1;ow++){//枚举ow
                    long long owo=f[i-1][id][ob][ow];//偷懒owo 
                    if(a[i]!=0)//如果涂白 
                        if(ob)//如果有奇黑 
                            f[i][id][ob][ow]=(f[i][id][ob][ow]+fx[i-2]*owo%mod)%mod,//偶白 
                            f[i][id^1][ob][1]=(f[i][id^1][ob][1]+fx[i-2]*owo%mod)%mod;//奇白（奇白就肯定为1了） 
                        else
                            f[i][id^1][ob][1]=(f[i][id^1][ob][1]+fx[i-1]*owo%mod)%mod;//没有奇黑，只能转移到奇白 
                    if(a[i]!=1)//如果涂黑 
                        if(ow)//如果有奇白 
                            f[i][id][ob][ow]=(f[i][id][ob][ow]+fx[i-2]*owo%mod)%mod,//偶黑
                            f[i][id^1][1][ow]=(f[i][id^1][1][ow]+fx[i-2]*owo%mod)%mod;//奇黑（奇黑就肯定为1了）
                        else
                            f[i][id^1][1][ow]=(f[i][id^1][1][ow]+fx[i-1]*owo%mod)%mod;//没有奇白，只能转移到奇黑 
                }
    printf("%lld",(f[n][p][0][0]+f[n][p][0][1]+f[n][p][1][0]+f[n][p][1][1])%mod);
    //直接计算答案 
}