Solution P10175 / 模数性质与分配律展开
BreakPlus
·
·
题解
验题人题解。
枚举 |S|，然后我们知道了每一个 a_i+|S|，暴力跑一遍 \mathcal{O}(n^2) 的树上背包即可。设 f_{i,j} 为以 i 为根的子树选取了大小为 j 的连通块，每种方案 \prod(a_i+|S|) 的总和，易转移。
发现每次枚举 |S| 其实制造了浪费，又有模数为 U^V 的性质没有使用。
好像只寄希望于它变成 $0$ 并没有什么用。
继续尝试，为了让每个式子里出现 $U$，同时联想到分配律展开的 trick，我们可以将乘积中的每个数写成除以 $U$ 的带余除法形式：令 $a_i+|S| = Ux+y \ (0 \le y < U)$。
我们惊喜地发现，一堆 $(Ux+y)$ 的乘积看成每个括号中选取一项乘起来再加和（分配律）的形式后，若 $Ux$ 的选取个数不少于 $V$ 个，那么整个这一项模 $U^V$ 就变成 $0$ 了。
为了方便实现，由于 $a_i$ 已经确定，我们不必去拆 $a_i$，而只把 $|S|$ 写成 $Ux+y$ 的形式，则 $\prod (a_i+|S|) = \prod (Ux + (y+a_i))$。
$y$ 的取值范围是很小的，启发我们直接枚举 $y$，然后 DP 时记录选取 $Ux$ 的次数（最多 $V-1$ 次）。而 $Ux$ 具体是多少，我们可以最后再计算，它对整个 DP 过程是不影响的！
此时我们就不需要 24 分做法中的枚举 $|S|$，而是枚举 $|S| \mod U$ 再 DP。
设 $f_{i,j,y,k}$ 表示以 $i$ 为根，选取 $j$ 个点的连通块，枚举的 $|S| \mod U = y$，选取 $Ux$ 的个数为 $k(k<V)$，树上背包转移它。
DP 完后再枚举 $|S|$ 具体的值，此时 $|S| = Ux+y$ 中 $x,y$ 的具体值已经确定，直接访问 $f$ 数组加和计算即可。
```cpp
vector<ll>E[2005];
ll n,U,V,Mod,a[2005],p[2005],sz[2005],I; ll f[2001][2001][7], tmp[2001][7];
void dfs(ll x){
f[x][1][0] = (a[x] + I) % Mod;
f[x][1][1] = 1;
sz[x]=1;
for(auto y: E[x]){
dfs(y);
memset(tmp,0,sizeof(tmp));
for(ll j=0;j<V;j++){
for(ll k=1;k<=sz[x];k++){
for(ll l=0;j+l<V;l++){
for(ll k2=0; k2<=sz[y]; k2++)
tmp[k+k2][j+l] += f[x][k][j] * f[y][k2][l];
}
}
}
sz[x] += sz[y];
for(ll k=1;k<=sz[x];k++)
for(ll j=0;j<V;j++) f[x][k][j] = tmp[k][j] % Mod;
}
f[x][0][0] = 1;
}
void solve(){
n=read(), U=read(),V=read(), Mod=1;
for(ll i=1;i<=V;i++) Mod*=U;
for(ll i=2;i<=n;i++) p[i]=read(), E[p[i]].emplace_back(i);
for(ll i=1;i<=n;i++) a[i]=read();
ll ans = 0;
for(I=0;I<U;I++){
memset(f,0,sizeof(f));
dfs(1);
for(ll x=1;x<=n;x++){
for(ll i=I+((I==0)?U:0);i<=sz[x];i+=U){
ll p=i/U*U, w=1;
for(ll j=0;j<V;j++){
ans = (ans + f[x][i][j] * w);
w = w * p % Mod;
}
}
ans %= Mod;
}
}
printf("%lld\n", ans);
}
```