A.小 ω 的距离
经典数据随机，期望每次减少一半，直接暴力往前跳就行。
B.小 ω 的匹配
读懂题了就很简单了，容易发现每行只有前 \(m\) 个数有用，于是我们得到一个 \(m\times m\) 的网格，第 \(i\) 行选择一个数 \(j\)，使得这 \(m\) 个前缀的并等于这 \(m\) 个数的并，并且并集集合大小为 \(m\)，这个东西直接搜大概是 \(m!\) 的，由于 \(m\) 最大为 \(10\)，然后就过了。
C.小 ω 的树
赛时式子转化错了，一个半小时狂砍 \(0\) 分。
问：如果没转化错能切吗？
答：会切的！
首先运用乘法分配律把贡献拆开，然后树形 \(dp\)。
具体的，设 \(f_{x,i,j}\) 代表 \(x\) 子树内有 \(i\) 个未匹配的点且贡献为 \(1\)（后面称为不做贡献，因为是相乘），有 \(j\) 个未匹配点且贡献为对应的 \(a\)，合并子树时分四种情况：作 \(\text{LCA}\) 且作贡献，作 \(\text{LCA}\) 且不做贡献，不作 \(\text{LCA}\) 且作贡献，不作 \(\text{LCA}\) 且不作贡献。
点击查看代码
#include <bits/stdc++.h>
#define fr first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 110;
struct edge{int to,pre;}e[N<<1];
int a[N],las[N],cnt,siz[N],P;
LL tmp[N][N][2],g[N][N][2],f[N][N][N],s1[N][N],s2[N][N];
void add(int u,int v){e[++cnt] = {v,las[u]},las[u] = cnt;}
inline int mod(int x){return x >= P ? x-P : x;}
void D(int x,int fa)
{
for (int i = las[x],y;i;i = e[i].pre)
if ((y = e[i].to) != fa) D(y,x);
g[0][0][0] = s1[0][0] = 1;
for (int i = las[x],y;i;i = e[i].pre)
{
if ((y = e[i].to) != fa)
{
for (int u = 0;u <= siz[x];u++)
{
for (int v = 0;v+u <= siz[x];v++)
{
for (int p = 0;p <= siz[y];p++)
{
for (int q = 0;q+p <= siz[y];q++)
{
tmp[u+p][v+q][0] = (tmp[u+p][v+q][0]+g[u][v][0]*f[y][p][q])%P,
tmp[u+p][v+q][1] = (tmp[u+p][v+q][1]+g[u][v][1]*f[y][p][q])%P;
if (p)
tmp[u+p-1][v+q][0] = (tmp[u+p-1][v+q][0]+g[u][v][0]*f[y][p][q]%P*p)%P,
tmp[u+p-1][v+q][1] = (tmp[u+p-1][v+q][1]+g[u][v][1]*f[y][p][q]%P*p)%P;
if (q) tmp[u+p][v+q-1][1] = (tmp[u+p][v+q-1][1]+g[u][v][0]*f[y][p][q]%P*q)%P;
s2[u+p][v+q] = (s2[u+p][v+q]+s1[u][v]*f[y][p][q])%P;
}
}
}
}
siz[x] += siz[y];
for (int u = 0;u <= siz[x];u++)
for (int v = 0;v+u <= siz[x];v++)
g[u][v][0] = tmp[u][v][0],g[u][v][1] = tmp[u][v][1],tmp[u][v][0] = tmp[u][v][1] = 0,s1[u][v] = s2[u][v],s2[u][v] = 0;
}
}
for(int u = 0;u <= siz[x];u++)
for(int v = 0;v+u <= siz[x];v++)
f[x][u][v] = mod(f[x][u][v]+g[u][v][1]),
f[x][u][v] = (f[x][u][v]+g[u][v][0]*a[x])%P,
f[x][u+1][v] = mod(f[x][u+1][v]+s1[u][v]),
f[x][u][v+1] = (f[x][u][v+1]+s1[u][v]*a[x])%P,
g[u][v][0] = g[u][v][1] = s1[u][v] = 0;
siz[x]++;
}
int main()
{
int n = read();P = read();
for (int i = 1;i <= n;i++) a[i] = read();
for (int i = 1,u,v;i < n;i++)
u = read(),v = read(),add(u,v),add(v,u);
D(1,0);
cout << f[1][0][0];
return 0;
}
D.小 ω 的画作
Dora's Paint
我打 \(\text{CF3500}\)，真的假的？