杭电多校第六场（IF）

I - Divisibility（思维）

题意：

有命题：将 b 进制数y按位相加，循环无穷次，最终结果若%x == 0，则有y % x == 0，反之不然

给出b和x，判断命题是否成立

……打表发现的b % x == 1时成立，看到有数论大佬推出来的%%%

想看推导的右转https://www.cnblogs.com/lipoicyclic/p/13449188.html

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double PI = acos(-1.0);
const int N = 25;

int main() {
    int t;
    ll n, x;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &x);
        if(n % x == 1)
            printf("T\n");
        else
            printf("F\n");
    }
    return 0;
}

F - A Very Easy Graph Problem（最小生成树 + 树）

题意：

n个点m条边，第 i 条边的长度为2 ^ i，d(i, j) 表示 i、j 之间的最短路，[....]叫艾佛森括号，当括号内条件成立时为1，否则为0，求：

思路：

可以发现边的长度是递增的，并且任意一条边大于它之前所有边之和，所以构造一个最小的连通图，也就是树，树上两点距离也就是最短路了。每条边的贡献 = 该边左边的1节点数 * 右边的0节点数 * 边权 + 左边的0节点数 * 右边的1节点数 * 边权

参考：https://blog.csdn.net/hddddh/article/details/107849596

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const int N = 1e5 + 7;

struct node
{
    int v, next, w;
}edge[4 * N];

ll qpow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int fa[N], n, m, head[N], tot, cn1, cn0, vis[N];
ll dp[N][2], ans;

void init() {
    ans = 0, tot = 0, cn1 = 0, cn0 = 0;
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        head[i] = -1;
        dp[i][0] = dp[i][1] = 0;
    }
}

void add(int u, int v, int w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}

int Find(int x) {
    if(fa[x] != x) fa[x] = Find(fa[x]);
    return fa[x];
}

void Union(int x, int y) {
    int tmpx = Find(x);
    int tmpy = Find(y);
    if(tmpx != tmpy)
        fa[tmpx] = tmpy;
}

void dfs1(int u, int pre) {
    if(vis[u] == 1) dp[u][1] = 1;
    if(vis[u] == 0) dp[u][0] = 1;
    for(int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if(v == pre) continue;
        dfs1(v, u);
        dp[u][0] += dp[v][0];
        dp[u][1] += dp[v][1];
    }
}

void dfs2(int u, int pre) {
    for(int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        int w = edge[i].w;
        if(v == pre) continue;
        dfs2(v, u);
        ans = (ans + dp[v][0] * (cn1 - dp[v][1]) % mod * qpow(2, w)) % mod;//点v一侧的0点数和另一侧的1点数
        ans = (ans + dp[v][1] * (cn0 - dp[v][0]) % mod * qpow(2, w)) % mod;
    }
}

int main() {
    int t, u, v;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        init();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &vis[i]);
            if(vis[i] == 0) cn0++;
            else cn1++;
        }
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            if(Find(u) == Find(v)) continue;
            Union(u, v);
            add(u, v, i);
            add(v, u, i);
        }
        dfs1(1, -1);
        dfs2(1, -1);
        printf("%lld\n", ans);
    }
    return 0;
}