7.5 模拟赛小记

A.方格填数 4 - 填错了

洛谷 P3197 [HNOI2008] 越狱

n 个格子，一排，能填 1 ~ m，求填数时左右相邻的格子出现相同数的方案数。

正难则反，补集转换。容易想到所有方案数减去相邻格子没有出现相同数的方案数。

那么没填错的方案数：$m \times (n - 1) ^ {m - 1}$。即第一个格子有 m 种选法，后 n - 1 个格子为了和前面的不一样所以各有 m - 1 个选法。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 100003;
int a, b;
int ksm(int x, int y)
{
    int tot = 1;
    while(y)
    {
        if(y & 1) tot = (tot * x) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return tot % mod;
}
signed main()
{
    scanf("%lld%lld", &a, &b);
    printf("%lld", ((ksm(a, b) % mod) - a* ksm(a - 1, b - 1) % mod + mod) % mod);
    return 0;
}

B.分组

洛谷 P3043 [USACO12JAN] Bovine Alliance G

前言：翻译的什么依托答辩。看着样例才猜出来题意。搁这考阅读理解呢？

题意：每个点独自领导一个小组。每条边可以分其两个端点所在的组中任意一个。要求每个组最多只能有一条边。

根据题意，就是找找连通块，用并查集。甚至不用建图。

发现只有三种情况：基环树、无根树、（不是环和链）其他（每个点均连了两个以上的边）。长这样：

对于基环树，可能的答案形态：

发现只是基环树中环的那部分，可以都选左半边的边，反之亦然。故基环树时只有两种方案;

对于无根树，可能的答案形态：

发现无根树中，总有一个点的组中没有边。于是有 n 种方案。

其他不符合要求，不贡献答案。然后把每部分的连通块求出来的答案相乘就是总方案数。

总的来说，数据结构 + 组合数学感觉是比较有意思的题目（对我来说）。反正戳着我的知识盲区了。考场只会写爆搜。

附：我图论从一开始就没学懂，基础为 0，所以补充一下基环树、无根树的定义：

基环树：严格意义上讲并不算树。大概是树和环接起来的。把环破了就是一棵正常的树。

无根树：和普通树的形态一样，只是没有指定根节点。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, m;
int u, v;
ll ans = 1;
int f[N], d[N], b[N];
int vis[N], tot = 0;
int findd(int x)
{
    if(f[x] != x) f[x] = findd(f[x]);
    return f[x];
}
void init() {for(int i = 1; i <= n; i ++ ) {d[i] = 1;f[i] = i;}}
int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &u, &v);
        int uu = findd(u);
        int vv = findd(v);
        if(uu == vv) b[vv]++;
        else
        {
            f[uu] = vv;
            d[vv] += d[uu];
            d[uu] = 0;
            b[vv] += b[uu] + 1;
        }
        if(! vis[u]) tot ++;
        if(! vis[v]) tot ++;
        vis[u] = vis[v] = 1;
    }
    if(tot < m)
    {
        puts("0");
        return 0;
    }
    for(int i = 1; i <= n; i ++ )
    {
        if(f[i] == i)
        {
            if(b[i] >= d[i]) ans = (ans << 1) % mod;
            else ans = ans * d[i] % mod;
        }
    }
    printf("%lld", ans);
    return 0;
}