A.方格填数 4 - 填错了
n 个格子，一排，能填 1 ~ m，求填数时左右相邻的格子出现相同数的方案数。
正难则反，补集转换。容易想到所有方案数减去相邻格子没有出现相同数的方案数。
那么没填错的方案数：$m \times (n - 1) ^ {m - 1}$。即第一个格子有 m 种选法，后 n - 1 个格子为了和前面的不一样所以各有 m - 1 个选法。
```cpp
#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.分组
前言：翻译的什么依托答辩。看着样例才猜出来题意。搁这考阅读理解呢？
题意：每个点独自领导一个小组。每条边可以分其两个端点所在的组中任意一个。要求每个组最多只能有一条边。
根据题意，就是找找连通块，用并查集。甚至不用建图。
发现只有三种情况：基环树、无根树、（不是环和链）其他（每个点均连了两个以上的边）。长这样：
对于基环树，可能的答案形态：
发现只是基环树中环的那部分，可以都选左半边的边，反之亦然。故基环树时只有两种方案;
对于无根树，可能的答案形态：
发现无根树中，总有一个点的组中没有边。于是有 n 种方案。
其他不符合要求，不贡献答案。然后把每部分的连通块求出来的答案相乘就是总方案数。
总的来说，数据结构 + 组合数学感觉是比较有意思的题目（对我来说）。反正戳着我的知识盲区了。考场只会写爆搜。
附：我图论从一开始就没学懂，基础为 0，所以补充一下基环树、无根树的定义：
基环树：严格意义上讲并不算树。大概是树和环接起来的。把环破了就是一棵正常的树。
无根树：和普通树的形态一样，只是没有指定根节点。
```cpp
#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;
}
```
end.