20230923 B 组 发怒 题解
前言
前三题比较水，虽然场上只写了 T1，T2 推出来了那个看起来很好维护的式子，以为自己能维护，结果要用一个叫高维前缀和的我不会的算法，硬刚 T2 3.5h，最终得分 100+0+0+0。
所以前三题我只写简略题解，第四题比较有意思。
前三题简略题解：
T1
删点不好维护，倒着加点，并查集维护，复杂度 $O((n+m)\log n)$。
T2
打表发现 $f^k_{0,0}=\bigoplus_{(i|j)\subseteq k}a_{i,j}$（其中 $|$ 表示按位或，$\bigoplus$ 表示按位异或，$\subseteq $ 表示二进制下 $1$ 的集合的从属关系），直接高维前缀和维护。
T3
考虑分成有空集和没空集两种情况，前一种贪心，后一种把式子化一下然后贪心。
T4
首先这道题长得很像树形 DP，那先考虑直接在树上做。
这里有个技巧，树上维护连通块可以考虑从上往下 DP（这么说可能有点抽象，详见状态设计）。
那么我们很容易设出一个状态，设 $dp_{rt,i,j}$ 表示考虑以 $rt$ 为根，考虑 dfs 序前 $i$ 个点，乘积为 $j$ 的方案数，转移枚举之前的乘积即可，具体转移方程略。
容易发现，为了不重不漏，我们只要对每个结点独立求出它子树内的答案即可，那么显然可以把第一维压掉，所以设 $dp_{i,j}$，意义和上文相同。
这样复杂度上界是 $O(n^2m)$ 的（考虑一条链），那么考虑优化。
首先这个 $m$ 应该先优化掉，因为第二维只和乘法有关，那么我们可以考虑除法下取整的一个性质，即 $\left\lfloor\frac{\left\lfloor\frac{x}{n}\right\rfloor}{m}\right\rfloor=\left\lfloor\frac{x}{nm}\right\rfloor$，那么我们可以把第二维改为维护 $\left\lfloor\frac{m}{j}\right\rfloor$，这样第二维的取值就只有 $\sqrt{m}$ 种了。
然后是前面的 $n^2$，容易发现这个数其实和树的形态有关，那么我们可以考虑使用点分治优化成 $O(n\log n)$ 的。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2005,mod=1e9+7;
int n,m,a[N],vis[N],ans,tt;
vector<int> e[N];
struct svsqrt{// (1)!
int a[N];
void clear(){
mem(a,0);
}
int& operator [](const int &r){
if(r<=tt) return a[r];
else return a[tt+m/r];
}
int calc(){
int res=0;
forup(i,0,N-1){
(res+=a[i])%=mod;
}
return res;
}
};
int als,sz[N],mx[N],wq;
void getrt(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(vis[i]||i==fa) continue;
getrt(i,x);
sz[x]+=sz[i];
mx[x]=max(mx[x],sz[i]);
}
mx[x]=max(mx[x],als-sz[x]);
if(!wq||mx[x]<mx[wq]) wq=x;
}
vector<int> ss;
void dfs(int x,int fa,svsqrt& dp){
sz[x]=1;
svsqrt nw;nw.clear();
for(auto i:ss){
if(i<a[x]) continue;
if(!dp[i]) continue;
(nw[i/a[x]]+=dp[i])%=mod;
}
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs(i,x,nw);
sz[x]+=sz[i];
}
for(auto i:ss){
if(!nw[i]) continue;
(dp[i]+=nw[i])%=mod;
}
}
void dfz(int x){
svsqrt dp;
dp.clear();
dp[m]=1;
dfs(x,0,dp);
(ans+=dp.calc()-1)%=mod;
vis[x]=1;
for(auto i:e[x]){
if(vis[i]) continue;
als=sz[i];
wq=0;
getrt(i,0);
dfz(wq);
}
}
signed main(){
n=read();m=read();
fordown(i,m,1){
if(m/i!=m/(i+1)) ss.push_back(m/i);
}
forup(i,1,n){
a[i]=read();
}
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
tt=sqrt(m)+5;
wq=0;
als=n;
getrt(1,0);
dfz(wq);
printf("%d\n",ans);
}
- 非常方便的写法，除了处理除法下取整以外改一改还能处理负数下标