D - Rebuild Tree
Description
给出一个(n(nleq5 imes10^4))个点的树，从中删去(k(kleq100))条边，再任加(k)条边，使得其仍是一棵树，求方案数。
Solution
prufer序列+推推推。
删去(k)条边之后树就变成了(k+1)个连通块，设每块的大小为(s_i)。把每一块视为一个大点，则由其构成的树对应一个长度为((k+1)-2)的prufer序列。由于两个块(i,j)之间连边的方案数是(s_is_j)，那么这棵树对应的方案数即为(prod s_i^{c_i+1}=prod s_i^{c_i}prod s_i)，其中(c_i)为prufer序列中(i)的出现次数，即度数-1。在(prod s_i^{c_i}prod s_i)中，后一项是和prufer序列无关的，那么只需考虑前一项，即求(t=sum_{prufer(k-1)}prod s_i^{c_i})，其中(prufer(n))表示一个长度为(n)的prufer序列。
当在prufer序列的一个位置上填(i)时，会使得(c_i)加一，对(t)的贡献是(s_i)。具体来说：
那么答案即为(ans=sum_{split}tprod s_i=n^ksum_{split}prod s_i)，该(sum)可以转化为：将树删掉(k)条边，每块选择一个点的方案数。那么可以用树形DP解决：设(f(u,i,0/1))表示以(u)为根的子树被删了(i)条边，(u)所在的这一块还未/已经选点。
时间复杂度(O(nk^2))，树形DP里面根据子树大小优化一下就能过。
Code
//Rebuild Tree
#include <cstdio>
#include <vector>
using std::vector;
typedef long long lint;
const int N=5e4+10;
const int K=100+10;
const int P=998244353;
lint fpow(lint x,int y) {lint r=1; for(y;y;y>>=1,x=x*x%P) if(y&1) r=r*x%P; return r;}
int n,k; vector<int> e[N];
int siz[N];
lint f[N][K][2]; lint tmp[K][2];
void dp(int u,int fa)
{
siz[u]=1;
f[u][0][0]=1,f[u][0][1]=1;
for(int v:e[u])
{
if(v==fa) continue;
dp(v,u);
for(int i=0;i<siz[u];i++)
for(int j=0;j<siz[v]&&i+j<=k;j++)
{
tmp[i+j][0]=(tmp[i+j][0]+f[u][i][0]*f[v][j][0])%P;
tmp[i+j][1]=(tmp[i+j][1]+f[u][i][1]*f[v][j][0]+f[u][i][0]*f[v][j][1])%P;
tmp[i+j+1][0]=(tmp[i+j+1][0]+f[u][i][0]*f[v][j][1])%P;
tmp[i+j+1][1]=(tmp[i+j+1][1]+f[u][i][1]*f[v][j][1])%P;
}
siz[u]+=siz[v];
for(int i=0;i<siz[u];i++)
{
f[u][i][0]=tmp[i][0],f[u][i][1]=tmp[i][1];
tmp[i][0]=tmp[i][1]=0;
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n-1;i++)
{
int u,v; scanf("%d%d",&u,&v);
e[u].push_back(v),e[v].push_back(u);
}
dp(1,0);
printf("%lld
",fpow(n,k-1)*f[1][k][1]%P);
return 0;
}
E - Tree Xor
Description
给出一个(n(nleq10^5))阶树，点有未知的点权(w_i(<2^{30}))，已知每个点点权的范围([L_i,R_i])和每条边两边点权的异或值，求可能的方案数。
Solution
首先DFS一遍，得到根到每个点的异或值(a_i)，实际上就是求根的点权(w_{rt})有多少种取法，即(|igcap[L_i,R_i]oplus a_i|)。运用trie树的想法，对于第(i)个点，先找到(L_i)与(R_i)的分歧的那一位，然后从下一位开始，先沿着(L_i)跑再沿着(R_i)跑。沿着(L_i)跑的时候，若(L_i)的这位是0，例如(L_i=11010????)，那把这位变成1的数都在范围内，即(11011????in[L_i=11010????,R_i])，将其异或(a_i)就得到(w_{rt})的一个取值范围。同理，沿着(R_i)跑的时候，若(R_i)的这位是1，那把这位变成0的数都在范围内。这样([L_i,R_i]oplus a_i)就变成了(O(logw))个区间，对每个(i)对应的这(O(logw))个区间求交即可，可以排序+离散化也可以用线段树。
时间复杂度(O(nlogwcdot logn))。
Code
//Tree Xor
#include <cstdio>
#include <vector>
using std::vector;
typedef std::pair<int,int> pII;
int bit(int x,int k) {return (x>>k)&1;}
int lowbit(int x) {return x&(-x);}
const int N=1e5+10;
int n; pII lim[N];
vector<pII> e[N];
const int A=(1<<30)-1;
int a[N];
void dfs(int u,int fa)
{
for(pII p:e[u])
{
int v=p.first,w=p.second;
if(v==fa) continue;
a[v]=a[u]^w,dfs(v,u);
}
}
const int N0=N*50;
int rt,ndCnt,ch[N0][2]; int tag[N0];
int optL,optR;
void ins(int &p,int L0,int R0)
{
if(!p) p=++ndCnt,tag[p]=0;
if(optL<=L0&&R0<=optR) {tag[p]+=1; return;}
int mid=L0+R0>>1;
if(optL<=mid) ins(ch[p][0],L0,mid);
if(mid<optR) ins(ch[p][1],mid+1,R0);
}
int ans=0;
void segDfs(int p,int L0,int R0,int x)
{
if(!p) return;
x+=tag[p];
if(x==n&&ch[p][0]+ch[p][1]==0) {ans+=(R0-L0+1); return;}
int mid=L0+R0>>1;
segDfs(ch[p][0],L0,mid,x),segDfs(ch[p][1],mid+1,R0,x);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&lim[i].first,&lim[i].second);
for(int i=1;i<=n-1;i++)
{
int u,v,w; scanf("%d%d%d",&u,&v,&w);
e[u].push_back(pII{v,w}),e[v].push_back(pII{u,w});
}
a[1]=0,dfs(1,1);
optL=lim[1].first,optR=lim[1].second,ins(rt,0,A);
for(int i=2;i<=n;i++)
{
int x0=0,k0=29; int L=lim[i].first,R=lim[i].second;
while(bit(L,k0)==bit(R,k0)) x0|=(bit(L,k0)^bit(a[i],k0))<<k0,k0--;
for(int k=k0-1,x=x0|(0^bit(a[i],k0))<<k0,y=L>>k0<<k0;k>=0;k--)
{
int b=bit(L,k);
if(b==0)
optL=x|((1^bit(a[i],k))<<k),optR=optL+(1<<k)-1,
ins(rt,0,A);
y|=b<<k,x|=(b^bit(a[i],k))<<k;
}
optL=optR=L^a[i],ins(rt,0,A);
for(int k=k0-1,x=x0|(1^bit(a[i],k0))<<k0,y=R>>k0<<k0;k>=0;k--)
{
int b=bit(R,k);
if(b==1)
optL=x|((0^bit(a[i],k))<<k),optR=optL+(1<<k)-1,
ins(rt,0,A);
y|=b<<k,x|=(b^bit(a[i],k))<<k;
}
optL=optR=R^a[i],ins(rt,0,A);
}
segDfs(rt,0,A,0);
printf("%d
",ans);
return 0;
}
G - Product
Description
给出(nleq50,kleq50,Dleq10^8)，求：(D!sum_{a_{1..n}}[a_i geq k and Sigma a_i=D+nk]prod_{i=1}^n1/a_i!)
Solution
首先进行一步转化：把(D)个位置分别填上([1,n])中的数⇔对于(iin[1,n])依次从剩余的位置选(a_i)个位置填上(i)。于是有：
利用容斥原理搞掉(exist a_t<k)的情况。先DP出(f[i,j])表示把(j)个位置分别填上([1,i])中的数且每种数的个数均小于(k)的方案数。钦定有(i)个(a_t<k)，其和为(j)，其余随意，那么此时的方案数(r[i,j])为(inom{n}{i}inom{D+nk}{j}f[i,j](n-i)^{D+nk-j})。其中(inom{n}{i})代表从([1,n])中选(i)个数，(inom{D+nk}{j})代表从(D+nk)个位置中选(j)个位置。容斥得到(sum_{i=0}^{n-1}(-1)^isum_j r[i,j])，再乘以(D!/(D+nk)!)即可。
时间复杂度(O(n^2k^2))。
Code
//Product
#include <cstdio>
const int P=998244353;
const int N=50+1;
typedef long long lint;
lint fpow(lint x,int y) {lint r=1; while(y) r=r*(y&1?x:1)%P,y>>=1,x=x*x%P; return r;}
int n,k,D;
lint ifac[N*N],C[N*N][N*N],CD[N*N];
void init(int n)
{
ifac[0]=1; for(int i=1;i<=n;i++) ifac[i]=1LL*ifac[i-1]*fpow(D+i,P-2)%P;
C[0][0]=C[1][0]=C[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
CD[0]=1; for(int i=1;i<=n;i++) CD[i]=(D+n-i+1)*fpow(i,P-2)%P*CD[i-1]%P;
}
lint f[N][N*N];
int main()
{
scanf("%d%d%d",&n,&k,&D); init(n*k);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=(i-1)*(k-1);j++)
for(int j1=0;j1<k;j1++)
f[i][j+j1]=(f[i][j+j1]+C[j+j1][j1]*f[i-1][j])%P;
lint ans=0;
for(int i=0;i<n;i++)
{
lint r=0;
for(int j=0;j<=i*(k-1);j++) r=(r+fpow(n-i,D+n*k-j)*CD[j]%P*f[i][j]%P)%P;
r=r*C[n][i]%P;
if(i&1) ans=(ans+P-r)%P; else ans=(ans+r)%P;
}
printf("%lld
",ans*ifac[n*k]%P);
return 0;
}