[Acwing] 第 49 场周赛

前言

传送门 :

4415. 点的赋值

题意 :

给定一个 无向无权图 , 对于每个节点你可以将其赋值 1 , 2 , 3 1,2,3 1,2,3 , 所有边两端的节点和必然需要是奇数,询问所有方案

思路 : 显然合法方案是 : ( 奇 数 − 偶 数 − 奇 数 − 偶 数 奇数 - 偶数-奇数-偶数 奇数−偶数−奇数−偶数)

因此考虑进行黑白染色 , 我们记录 黑色的数量 c n t 1 cnt_1 cnt1​,白色的数量 c n t 2 cnt_2 cnt2​

对于奇数有两种选择 , 而奇数既可以放黑色也可以放白色

因此对于一个连通块内 的 答案就是 2 c n t 1 + 2 c n t 2 2^{cnt_1} +2^{cnt_2} 2cnt1​+2cnt2​

(当然有个呆瓜歪成树 d p dp dp

code :

const int maxn = 3e5 + 5, mod = 998244353;
int h[maxn], e[2*maxn], ne[2*maxn], idx;
int c[maxn];
int n, m, cnt1, cnt2;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool dfs(int i, int color){
    c[i] = color;
    if (color == 1) cnt1++;
    else cnt2++;
    for(int j = h[i];j!=-1;j=ne[j]){
        int to = e[j];
        if(c[to]==color) return false;
        if(!c[to]){
            if(!dfs(to,3-color))
                return false;
        }
    }
    return true;
}

int qpow(int a, int b, int mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        for(int i = 1; i > a >> b;
            add(a,b);
            add(b,a);
        }        
        int flag = 0;
        LL res = 1;
        for(int i = 1; i