1.) 欧拉回路
打表找规律，打了斯特林，打了组合数，找不出，弃疗。我太蠢了，这题和前面这些东西没什么关系啊。考虑 (n) 个点时的完全图 (n cdot (n - 1) / 2) 条边，每条边选与不选两种决策，所以可以得到神奇的数字 (2^{n(n-1)/2}) ，而答案就是 (2^{(n-1)(n-2)/2}) 。具体证的话，对于 (n) 个点的图，拿出一个点，把 (n-1) 个点胡乱连边，方案数 (2^{(n-1)(n-2)/2}) 。然后让单独拿出来的点与其他点连边。如果某点度数是奇度就把单独拿出来的点与这个点连一条边，否则不连。这样的话，连边方案是唯一的。可以得到：A.) 除了单独拿出来的点外，其他点的度数在连边后为偶数。同时：B.) 根据无向图性质，所有点度数之和为偶数。由 A 和 B 可以得到，单独拿出来的点的度数也为偶数。因为每个点度数都是偶数，所以这样构造的 (n) 个点的图含有欧拉回路。并且这样显然会不遗漏地讨论完所有方案。呼……
#include <cstdio>
typedef long long ll;
const ll MOD = 998244353ll;
ll mul(ll a, ll b)
{
ll t = 0;
while (b) {
if (b & 1)
t = (t + a) % MOD;
b >>= 1;
a = (a << 1) % MOD;
}
return t;
}
ll mont(ll a, ll b)
{
ll t = 1;
a %= MOD;
while (b) {
if (b & 1)
t = mul(t, a);
b >>= 1;
a = mul(a, a);
}
return t;
}
int main()
{
ll n;
scanf("%lld", &n);
if (n == 1) {
printf("1
");
return 0;
}
ll ans;
if (n & 1)
ans = mont(mont(2, (n-1)/2), n-2);
else
ans = mont(mont(2, (n-2)/2), n-1);
printf("%lld
", ans);
return 0;
}
2.) 乌鸦坐飞机
ljh 大佬考场上想的线段树优化建图，多么窒息的操作……我非常幸运地一眼看出考倍增，然后玄学写错爆 0 ，考完重写了一次就 A 了，暂时不知道错哪。
推一下 dp 方程 (f_i = min{f_j + w_i}) ，要求 (j) 在 (i) 到根的路径上。发现是树上极值查询，所以就是倍增啊。
#include <stdio.h>
#include <stack>
#include <cstring>
#include <vector>
#include <cmath>
#include <ctype.h>
using namespace std;
typedef long long ll;
const int _N = 320000;
const int _lgN = 21;
vector<int> G[_N];
int dad[_N][_lgN], D[_N], W[_N], depth[_N], LG[_N], N, lgN;
ll f[_N][_lgN], ans[_N];
int moveup(int p, int s)
{
for (int i = 0; i <= lgN; ++i)
if ((s >> i) & 1) p = dad[p][i];
return p;
}
void dfs(int p, int d)
{
if (p != 1) {
depth[p] = depth[d] + 1;
dad[p][0] = d;
f[p][0] = ans[d];
for (int i = 1; i <= lgN; ++i) {
dad[p][i] = dad[dad[p][i-1]][i-1];
f[p][i] = min(f[p][i-1], f[dad[p][i-1]][i-1]);
}
int x = min(D[p], depth[p]);
int tmp = moveup(p, x-(1<<LG[x]));
ans[p] = min(f[tmp][LG[x]], f[p][LG[x]]) + W[p];
}
for (int i = G[p].size()-1; i >= 0; --i) {
int v = G[p][i];
if (v != d) dfs(v, p);
}
return;
}
int main()
{
scanf("%d", &N);
for (int x, y, i = 1; i < N; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
scanf("%d%d", &W[i], &D[i]);
lgN = log2(N + 0.5) + 1;
LG[0] = -1;
for (int i = 1; i <= N; ++i)
LG[i] = LG[i >> 1] + 1;
dfs(1, 0);
int T;
scanf("%d", &T);
while (T--) {
int x;
scanf("%d", &x);
printf("%lld
", ans[x]);
}
return 0;
}
3.) 四边形上树
真是妙啊。先考虑暴力，存在四边形的充要条件是任意三边和大于第四边。枚举四边形的最长边 (d) ，只要有 (a+b+c > d) 就可以了。直接把两点路径上的点排序，然后贪心地找到比枚举的 (d) 小的，最大的三个数，判断是否可以作为边长构成四边形。然后就是很精妙的操作了。推理可得，要构造出连续很多个数，还要使他们总是满足 (a+b+c leq d) 的话，当这些数的个数为 40 时，最大的数已经超过 int 上限了。所以对于路径长度 (>40) 的询问直接输出 (Yes) ，否则暴力排序并判断就好了。
#include <stdio.h>
#include <vector>
#include <algorithm>
const int _N = 120000;
const int X = 40;
using namespace std;
#define SC(a, b) (static_cast<a>(b))
typedef long long ll;
vector<int> G[_N];
int dad[_N], A[_N], B[_N], Bcnt, N;
bool mk[_N];
void dfs(int p)
{
for (int i = G[p].size()-1; i >= 0; --i) {
int v = G[p][i];
if (v != dad[p]) {
dad[v] = p;
dfs(v);
}
}
return;
}
int main()
{
int T;
scanf("%d", &N);
for (int i = 1; i <= N; ++i)
scanf("%d", &A[i]);
for (int x, y, i = 1; i < N; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
scanf("%d", &T);
dfs(1);
while (T--) {
int ins, x, y;
scanf("%d%d%d", &ins, &x, &y);
if (ins == 1) {
A[x] = y;
} else {
int a, i;
for (a = x, i = 1; i <= X; ++i)
mk[a] = 1, a = dad[a];
for (a = y, i = 1; i <= X && !mk[a]; ++i)
a = dad[a];
if (!mk[a] || !a) {
printf("Yes
");
for (a = x, i = 1; i <= X; ++i)
mk[a] = 0, a = dad[a];
continue;
}
int lca = a;
Bcnt = 0;
for (a = x; a != lca; a = dad[a])
B[++Bcnt] = A[a];
for (a = y; a != lca; a = dad[a])
B[++Bcnt] = A[a];
B[++Bcnt] = A[lca];
if (Bcnt < 4) {
printf("No
");
} else {
sort(B+1, B+1+Bcnt);
for (i = 4; i <= Bcnt; ++i)
if (SC(ll, B[i-3])+B[i-2]+B[i-1] > SC(ll, B[i])) break;
if (i == Bcnt+1)
printf("No
");
else
printf("Yes
");
}
for (a = x, i = 1; i <= X; ++i)
mk[a] = 0, a = dad[a];
}
}
return 0;
}