【考试总结】2022-03-20
签到
枚举哪些位置超出了限制，注意这里需要将 \(n\) 减 \(1\)，那么可以直接列出答案的计算表达式
\[\sum_{S\subseteq U}(-1)^{|S|}\binom{n+m+(c-1)|S|-\sum\limits_{x\in S} b^{x}}{m} \]如果我们可以保证 \(A=n+m+(c-1)|S|\ge \sum\limits_{x\in S} b^{x}\)，那么组合数是关于 \(\sum\limits_{x\in S} b^x\) 的多项式
枚举 \(|S|\) 以及 \(\sum\limits_{x\in S} b^x\) 和 \(A\) 的 \(\rm LCP\)（十进制）及后面一位的数字
这里想要得到答案，还需要在低位求出关于 \(\sum b^i\) 的多项式在所有 \(S\) 中的每个次幂的和
用 \(\rm DP\) 来做：设 \(f_{k}[i][j]\) 表示考虑了 \(\{1,2\dots i\}\) 这些数字并选出了 \(j\) 个 \(b^x\) 并对第 \(k\) 次幂的自变量求和，转移使用二项式定理合并即可
注意需要写高精度除法，但是进制转换只用做一次，那么使用模拟竖式的方法是可行的
Code Display
int Bas=10;
struct node{
vector a;
inline int size(){return a.size();}
inline void adjust(){
int siz=a.size();
for(int i=0;i=Bas){
a.emplace_back(a[siz-1]/Bas);
a[siz-1]%=Bas;
++siz;
}
while(siz>1&&!a[siz-1]) a.pop_back(),--siz;
return ;
}
inline int toint(int Mod=mod){
int siz=a.size(),res=0;
for(int i=siz-1;i>=0;--i) res=(res*Bas+a[i])%Mod;
return res;
}
inline void init(string x){
vector num[2]; num[0].resize(x.size());
int cur=0;
int len=x.size();
for(int i=len-1;i>=0;--i) num[cur][i]=x[i]-'0';
reverse(num[cur].begin(),num[cur].end());
while(num[cur].size()>1||num[cur][0]>0){
num[cur^1].clear();
int tmp=0,siz=num[cur].size();
bool flag=0;
for(int i=siz-1;i>=0;--i){
tmp=tmp*10+num[cur][i];
if(tmp>=Bas) flag=1;
if(flag) num[cur^1].emplace_back(tmp/Bas),tmp%=Bas;
}
a.emplace_back(tmp);
cur^=1;
reverse(num[cur].begin(),num[cur].end());
siz=num[cur].size(); num[cur].emplace_back(0);
for(int i=0;i>str_n;
n.init(str_n); n=n-1;
pw[0][0]=1; rep(i,1,2000) pw[0][i]=1;
for(int i=1;i<=2000;++i){
pw[i][0]=1;
pw[i][1]=mul(pw[i-1][1],b);
for(int j=2;j<=2000;++j) pw[i][j]=mul(pw[i][j-1],pw[i][1]);
}
dp[0][0][0]=1;
for(int k=0;k<=m;++k){
for(int i=1;i<=m;++i){
for(int j=0;j<=i;++j){
int sum=dp[i-1][j][k];
if(j) for(int t=0;t<=k;++t) ckadd(sum,mul(C[k][t],mul(dp[i-1][j-1][t],pw[i][k-t])));
dp[i][j][k]=sum;
}
}
}
for(int S=0;S<=m;++S){
node A,n_m,n_S,n_c;
n_m.init(m);
n_S.init(S);
n_c.init(abs(1-c));
if(c<0&&n+n_m >tmp(m);
for(int i=0;iS) break;
vector pwh(1+m);
pwh[0]=1;
for(int i=1;i<=m;++i) pwh[i]=mul(pwh[i-1],hig);
int tmp=0;
for(int k=0;k<=m;++k){
int sumx=0;
for(int t=0;t<=k;++t) ckadd(sumx,mul(C[k][t],mul(pwh[k-t],dp[lcp-1][S-cnt][t])));
ckadd(tmp,mul(poly[k],sumx));
}
ckadd(sum,tmp);
}
if(A.a[lcp]==1) ++cnt,ckadd(hig,pw[lcp][1]);
if(A.a[lcp]>1) break;
}
if(S&1) ckdel(ans,sum); else ckadd(ans,sum);
}
print(ans); putchar('\n');
return 0;
}
数据结构
将树拍到 \(\rm DFS\) 序上考虑，序列上的带权中点一定在带权重心的子树内，写倍增判定即可
卡常，所以用了 zkw线段树
我还有一个非常麻烦的使用 新重心在两个原来重心的路径上 的结论的方法，比这个垃圾到不知道哪里去了
Code Display
vector G[N];
int n;
int fa[N],dep[N],siz[N],top[N],son[N],dfn[N],ord[N],tim;
int bz[N][20];
inline void dfs2(int x,int topf){
top[x]=topf; ord[dfn[x]=++tim]=x; if(son[x]) dfs2(son[x],topf);
for(auto t:G[x]) if(!dfn[t]) dfs2(t,t);
}
inline void dfs1(int x,int fat){
dep[x]=dep[fa[x]=fat]+(siz[x]=1);
bz[x][0]=fat;
for(int i=1;bz[x][i-1];++i) bz[x][i]=bz[bz[x][i-1]][i-1];
for(auto t:G[x]) if(t!=fat){
dfs1(t,x); siz[x]+=siz[t];
if(siz[t]>siz[son[x]]) son[x]=t;
} return ;
}
ll nec;
struct Seg{
#define ls p<<1
#define rs p<<1|1
int lim;
ll sum[N<<2],tag[N<<2];
inline void build(int n){
lim=1;
while(lim<=(n+1)) lim<<=1;
return ;
}
inline void upd(int l,int r,ll v){
l+=lim-1; r+=lim+1;
int lc=0,rc=0;
for(int len=1;l!=r-1;l>>=1,r>>=1,len<<=1){
sum[l]+=lc*v; sum[r]+=rc*v;
if(!(l&1)) sum[l^1]+=len*v,tag[l^1]+=v,lc+=len;
if(r&1) sum[r^1]+=len*v,tag[r^1]+=v,rc+=len;
}
while(l){
sum[l]+=lc*v; sum[r]+=rc*v;
l>>=1; r>>=1;
}
return ;
}
inline ll Query(int l,int r){
ll res=0,rc=0,lc=0;
l+=lim-1; r+=lim+1;
for(int len=1;l!=r-1;r>>=1,l>>=1,len<<=1){
res+=tag[l]*lc+tag[r]*rc;
if(r&1) res+=sum[r^1],rc+=len;
if(!(l&1)) res+=sum[l^1],lc+=len;
}
while(l){
res+=tag[l]*lc+tag[r]*rc;
l>>=1; r>>=1;
}
return res;
}
#undef ls
#undef rs
#undef lson
#undef rson
}T;
signed main(){
freopen("yyl.in","r",stdin); freopen("yyl.out","w",stdout);
n=read();
rep(i,1,n-1){
int u=read(),v=read();
G[u].push_back(v); G[v].emplace_back(u);
}
int Q=read();
dfs1(1,0); dfs2(1,1); T.build(n);
while(Q--){
if(read()-1){
int u=read(),v=read(),w=read();
while(top[u]!=top[v]){
if(dep[top[u]]dep[v]) swap(u,v);
T.upd(dfn[u],dfn[v],w);
}else{
int x=read(),w=read();
T.upd(dfn[x],dfn[x]+siz[x]-1,w);
}
nec=T.sum[1]/2+1; //找到第一个大于等于 nec 的点即可
int l=1,r=n-1,pos=n;
while(l<=r){
int mid=(l+r)>>1;
if(T.Query(1,mid)>=nec) pos=mid,r=mid-1;
else l=mid+1;
}
int ans=ord[pos];
for(int i=19;~i;--i) if(bz[ans][i]){
int tar=bz[ans][i];
if(T.Query(dfn[tar],dfn[tar]+siz[tar]-1)<=T.sum[1]/2) ans=bz[ans][i];
}
if(T.Query(dfn[ans],dfn[ans]+siz[ans]-1)<=T.sum[1]/2) ans=fa[ans];
print(ans);
}
return 0;
}
爆搜
观察到 \(n\) 个点的无向图最多有 \(\frac n2\) 组匹配，将 \((2i,2i+1)\) 连一条虚边，那么所有的合法匹配一定将点集划分成了若干个环和链
使用虚边将 \((2i,2i+1)\) 绑定成一个虚点，使用 \(\Theta(2^{\frac n2}n^2)\) 的状压 \(\rm DP\) 来求每个集合表示成链/环的权值之和，剩下的工作是一个集合幂级数 \(\exp\)
\(\rm DP\) 链添加一维记录链尾，转移时因为 \((2i,2i+1)\) 被绑定，添加一组虚点的时候可以据此得到新的链尾，注意每条链会被计算正反两次
计算环的方案数时从环上最大标号的点开始 \(\rm DP\)，加入的一对虚点标号不超过当前集合最大值即可，也要记录环尾，最后通过环尾和集合内最大值是否有边判定是否合法即可
Code Display
const int N=40;
int n,m,C,G[N][N],inv[N],ifac[N],fac[N];
int chain[1<<18],cyc[1<<18],dp[1<<18][40];
inline int in(int S,int id){
return S>>(id>>1)&1;
}
struct FPS{
int p[19]; FPS(){memset(p,0,sizeof(p));}
FPS operator +(const FPS &a)const{
FPS res;
rep(i,0,m) res.p[i]=add(p[i],a.p[i]);
return res;
}
FPS operator -(const FPS &a)const{
FPS res;
rep(i,0,m) res.p[i]=del(p[i],a.p[i]);
return res;
}
}f[1<<18];
inline void Exp(int *f){
vector g(m+1);
g[0]=1;
for(int i=1;i<=m;++i){
for(int j=0;j>1))][k^1],mul(C,dp[i][j]));
}
}
}
for(int i=1;i>1))][k^1],mul(C,dp[i][j]));
}
}
}
for(int i=1;i>1;
for(int k=0;k>1;
for(int k=0;k