Codeforces Round 1336 简要题解

发现好久没写题解了，补几场cf的题解。

A. Linova and Kingdom

略

B. Xenia and Colorful Gems

略

C. Kaavi and Magic Spell

略

D. Yui and Mahjong Set

吐了，辛辛苦苦推了一年依次问$1?n$的算法，结果交上去WA了，又分析了半天发现只有当$n>5$的时候才能保证正确，于是怒膜题解去了。
题解的询问方式是先依次问$n?1,n?2,...,3$，然后再依次问$1,2,1$。
注意到我们问了$1$两次之后，一定能得到$a_1$（第二次问时考虑triplet的增量为$\left(\genfrac{}{}{0ex}{}{a_1+1}{2}\right)$，这个是可以唯一还原$a_1$的）。同时第一次问$1$时的straight增量为$a_2?(a_3+1)$，而第二次问$1$时的straight增量为$(a_2+1)?(a_3+1)$，因此容易得到$a_2$和$a_3$。
再注意到对于$i\ge 4$，若我们已经得到了$a_1?a_{i?1}$，那么容易根据问$i?2$时的straight增量得到$a_i$（减掉已知部分剩下$(a_{i?1}+1)?a_i$，直接除即可）。
这样就可以在$n$次操作后问出$a_1?a_n$了。时间复杂度为$\mathcal{O}(n)$。

#include <bits/stdc++.h>using namespace std;int a[105],b[105];
int num[105];int main() {
    int n;scanf("%d",&n);int x,y;scanf("%d%d",&x,&y);for(int i=n-1;i>2;i--) {
    printf("+ %d\n",i);fflush(stdout);scanf("%d%d",&a[i],&b[i]);} printf("+ %d\n",1);fflush(stdout);scanf("%d%d",&a[1],&b[1]);printf("+ %d\n",2);fflush(stdout);scanf("%d%d",&a[2],&b[2]);printf("+ %d\n",1);fflush(stdout);scanf("%d%d",&x,&y);x-=a[2];y-=b[2];a[2]-=a[1];b[2]-=b[1];a[1]-=a[3];b[1]-=b[3];for(int i=3;i<n;i++) {
    a[i]-=a[i+1];b[i]-=b[i+1];}for(int i=2;i<=n+1;i++)if ((i*(i-1)>>1)==x) num[1]=i-1;num[3]=y-b[1]-1;num[2]=b[1]/(num[3]+1);assert(num[1]>=0&&num[2]>=0&&num[3]>=0);for(int i=4;i<=n;i++) {
    int s=b[i-2];if (i>4) s-=num[i-3]*num[i-4];s-=(num[i-3]+(i==4))*(num[i-1]+1);num[i]=s/(num[i-1]+1)-(i<n);assert(num[i]>=0);}printf("! ");for(int i=1;i<=n;i++) printf("%d ",num[i]);printf("\n");fflush(stdout);return 0;
} 
/* 5 1 6 1 15 4 20 5 24 5 40 8 48 */ 

E2. Chiori and Doll Picking (hard version)

这题好神啊，膜了一天题解。
显然只用考虑线性基里的元素。令线性基大小为$k$，只用求出只使用线性基里元素的答案再乘上$2^{n?k}$即可。我们对线性基进行一点处理，使得每个里面的元素都在某一列为主元（该列只有它为$1$），此时元素为$a_1?a_k$。
当$k$小的时候显然有一个dfs所有元素的算法，用__builtin_popcountll()即可做到$\mathcal{O}(2^k)$求解。
当$k$大的时候一个算法是对于非主元的部分采用DP。大致是依次枚举每个数，记录$F[S][i]$表示考虑到当前数字，非主元部分异或和为$S$，主元部分有$i$个（也即恰好选了$i$个）的方案数，转移直接考虑这个数选不选即可。时间复杂度为$\mathcal{O}(k^2{2}^{m?k})$。平衡一下两个算法可以做到$\mathcal{O}(nm+m?2^{\frac{m}{2}})$的复杂度，只能通过E1。
考虑优化$k$大时的算法。
考虑用FWT求解。现在要求$p_c$，令线性基元素能表出的集合幂级数为$F$，$c$位二进制整数对应的集合幂级数为$G_c$，则$p_c=([x^0]IFWT(FWT(F)?FWT(G_c)))?2^{n?k}$（这里集合幂级数的乘法是点乘）。考虑$FWT(F)$，根据FWT的公式，$[x^S]FWT(F)={\sum }_i(?1{)}^{|i\wedge S|}([x^i]F)$。注意到$[x^i]F$只有当$i$能被线性表出的时候为$1$，否则为$0$。
那么考虑把$i$拆成$a$中元素的异或，此时可以把$(?1{)}^{|i\wedge S|}$拆开，容易证明$[x^S]FWT(F)$只有在$?1\le i\le k,|S\wedge a_i|\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$时为$2^k$，其余时候均为$0$。
也即，若将线性基里的元素写成一个$k?m$的矩阵$A$，将$S$按位写成长为$m$的列向量$x$，那么$[x^S]FWT(F)=2^k$当且仅当$Ax=0$（$\mathrm{m}\mathrm{o}\mathrm{d}2$意义下），也即$x$在$A$的解空间中。由于$rank(A)=k$，根据一点简单的线代知识，$A$的解空间的秩为$m?k$，且可知这样的$S$为$m?k$个数的张成。
又可以注意到$[x^S]G_c$只跟$|S|$有关，可以预先$\mathcal{O}(m^3)$DP出$g_{i,j}$表示当$c=i,|S|=j$时$[x^S]G$的值。那么直接dfs所有可能的$S$，算出每种$|S|$有多少个数，再乘上对应的系数即可。这部分时间复杂度为$\mathcal{O}(2^{m?k}+m^3)$。
那么与$k$小时的算法平衡一下即可做到$\mathcal{O}(nm+m^3+2^{\frac{m}{2}})$的时间复杂度，可以通过E2。

#include <bits/stdc++.h>
#define MOD 998244353 
#define inv2 499122177using namespace std;typedef long long ll;ll pow_mod(ll x,int k) {
    ll ans=1;while (k) {
    if (k&1) ans=ans*x%MOD;x=x*x%MOD;k>>=1;}return ans;
}ll C[60][60];void pre(int n) {
    for(int i=0;i<=n;i++) C[i][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}namespace LB {
    ll num[60];bool insert(ll x,int k) {
    for(int i=k-1;i>=0;i--)if ((x>>i)&1) {
    if (!num[i]) {
    num[i]=x;return 1;}else x^=num[i];}return 0;
}void gause(int k) {
    for(int i=k-1;i>=0;i--)if (num[i]) {
    for(int j=i+1;j<k;j++)if ((num[j]>>i)&1) num[j]^=num[i];}
}}int ans[60];ll a[60],b[60];
int up;void dfs1(int d,ll s) {
    if (d>up) {
    ans[__builtin_popcountll(s)]++;return;}dfs1(d+1,s);dfs1(d+1,s^a[d]);
}int cnt[60];void dfs2(int d,ll s) {
    if (d>up) {
    cnt[__builtin_popcountll(s)]++;return;}dfs2(d+1,s);dfs2(d+1,s^b[d]);
}bool vis[60];int main() {
    int n,m;scanf("%d%d",&n,&m);pre(m);for(int i=1;i<=n;i++) {
    ll x;scanf("%lld",&x);LB::insert(x,m);}LB::gause(m);int sz=0;for(int i=m-1;i>=0;i--)if (LB::num[i]) {
    a[++sz]=LB::num[i];vis[i]=1;}if (sz*2<=m) {
    up=sz;dfs1(1,0);}else {
    for(int i=0;i<m;i++)if (!vis[i]) {
    b[++up]=(1LL<<i);for(int j=i+1;j<m;j++)if (LB::num[j]&&(((LB::num[j])>>i)&1)) b[up]^=(1LL<<j);}dfs2(1,0);for(int i=0;i<=m;i++)for(int j=0;j<=i;j++)for(int k=0;k<=m-i;k++) ans[j+k]=(ans[j+k]+C[i][j]*C[m-i][k]%MOD*((j&1)?MOD-1:1)%MOD*cnt[i])%MOD;ll inv=pow_mod(inv2,up);for(int i=0;i<=m;i++) ans[i]=ans[i]*inv%MOD;}ll v=pow_mod(2,n-sz);for(int i=0;i<=m;i++) printf("%lld ",ans[i]*v%MOD);printf("\n");return 0;
}

F. Journey

跟NOI2018 D2T2很像，做过那个题的话思维上不存在太大的难度。
分选的两条链LCA是否相同讨论。
若LCA不相同，一定满足较浅的LCA是较深的LCA的祖先。那么枚举较深的LCA的链，显然另一条链只会跟它到LCA某侧的路径有交，因此一个端点在某个距LCA距离为$k$的点的子树中，而另一个端点在LCA的子树外，这可以用线段树合并方便地统计答案。
若LCA相同，如果此时选的两条链有一个端点为LCA或者不在两边都有交跟上面情况类似，只考虑两条链两个端点都在某两个特定子树中的情况。考虑把这些链在一边子树中的端点拿出来建一个虚树。考虑枚举两条链这边端点的LCA，做一个启发式合并，那么固定了一条链和当前枚举的LCA的话，就知道另一边LCA深度的下界了，此时跟它有贡献的链在另一边的端点在某个子树中，数据结构维护即可。
实际实现的时候可以用链分治替代启发式合并。具体来说考虑dfs虚树，dfs到一个点的时候先递归重儿子，再加入一端为这个点的链，再dfs轻儿子，这样只需要对dfs序开$\mathcal{O}(\log n)$个树状数组即可。
时间复杂度$\mathcal{O}(n\log n+q{\log }^{2}n)$。

#include <bits/stdc++.h>
#define FR first
#define SE second
#define lowbit(x) (x&-x)using namespace std;typedef long long ll;
typedef pair<int,int> pr;namespace SGT {
    const int Maxn=20000000;int ch[Maxn][2],size[Maxn],tot;inline int cpynode(int o) {
    tot++;ch[tot][0]=ch[o][0];ch[tot][1]=ch[o][1];size[tot]=size[o];return tot;
}int update(int l,int r,int o,int p) {
    o=cpynode(o);size[o]++;if (l==r) return o;else {
    int m=((l+r)>>1);if (m>=p) ch[o][0]=update(l,m,ch[o][0],p);else ch[o][1]=update(m+1,r,ch[o][1],p);return o;}
}int merge(int l,int r,int x,int y) {
    if (!x) return y;if (!y) return x;int o=++tot;size[o]=size[x]+size[y];if (l==r) return o;else {
    int m=((l+r)>>1);ch[o][0]=merge(l,m,ch[x][0],ch[y][0]);ch[o][1]=merge(m+1,r,ch[x][1],ch[y][1]);return o;}
}int query(int l,int r,int o,int lx,int rx) {
    if (!o) return 0;if (l>=lx&&r<=rx) return size[o];else {
    int m=((l+r)>>1);if (m>=rx) return query(l,m,ch[o][0],lx,rx);if (m<lx) return query(m+1,r,ch[o][1],lx,rx);return query(l,m,ch[o][0],lx,rx)+query(m+1,r,ch[o][1],lx,rx);}
}}struct BIT {
    int sumv[200005];void add(int x,int n,int num) {
    for(;x<=n;x+=lowbit(x)) sumv[x]+=num;
}int sum(int x) {
    int s=0;for(;x;x-=lowbit(x)) s+=sumv[x];return s;
}int sum(int l,int r) {
    return sum(r)-sum(l-1);
}};BIT tr[20];vector <int> e[200005];int fa[200005][20],dep[200005];
int dfn[200005],ed[200005],dfs_cnt;
int size[200005];void dfs1(int x) {
    dfn[x]=++dfs_cnt;size[x]=1;dep[x]=dep[fa[x][0]]+1;for(int i=0;i<e[x].size();i++)if (e[x][i]!=fa[x][0]) {
    int u=e[x][i];fa[u][0]=x;for(int j=1;j<20;j++) fa[u][j]=fa[fa[u][j-1]][j-1];dfs1(u);size[x]+=size[u];}ed[x]=dfs_cnt;
}int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);int d=dep[x]-dep[y];for(int i=0;i<20;i++)if ((d>>i)&1) x=fa[x][i];if (x==y) return x;for(int i=19;i>=0;i--)if (fa[x][i]!=fa[y][i]) {
    x=fa[x][i];y=fa[y][i];}return fa[x][0];
}int jump(int x,int d) {
    for(int i=0;i<20;i++)if ((d>>i)&1) x=fa[x][i];return x;
}ll ans;
int n,k;vector <pr> q[200005];
vector <int> vt1[200005];int root[200005];map <pr,int> mp;
vector <pr> vt2[200005];
pr num[200005];bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}int st[200005],val[200005];
vector <int> ee[200005],vt3[200005],vt4[200005];void dfs3(int x,int top,int d,int rt) {
    int son=0;for(int i=0;i<ee[x].size();i++)if (size[ee[x][i]]>size[son]) son=ee[x][i];if (son) dfs3(son,top,d,rt);for(int i=0;i<vt3[x].size();i++) {
    int u=vt3[x][i];vt4[top].push_back(u);int s=k-(dep[x]-dep[rt]);if (s<=0) ans+=tr[d].sum(dfn[rt],ed[rt]);else if (dep[u]-dep[rt]>=s) {
    int t=jump(u,dep[u]-dep[rt]-s);ans+=tr[d].sum(dfn[t],ed[t]);}tr[d].add(dfn[u],n,1);}for(int i=0;i<ee[x].size();i++)if (ee[x][i]!=son) {
    int u=ee[x][i];dfs3(u,u,d+1,rt);for(int i=0;i<vt4[u].size();i++) {
    int v=vt4[u][i];int s=k-(dep[x]-dep[rt]);if (s<=0) ans+=tr[d].sum(dfn[rt],ed[rt]);else if (dep[v]-dep[rt]>=s) {
    int t=jump(v,dep[v]-dep[rt]-s);ans+=tr[d].sum(dfn[t],ed[t]);}}for(int i=0;i<vt4[u].size();i++) {
    int v=vt4[u][i];vt4[top].push_back(v);tr[d].add(dfn[v],n,1);tr[d+1].add(dfn[v],n,-1);}vector<int>().swap(vt4[u]);}vector<int>().swap(ee[x]);vector<int>().swap(vt3[x]);
}void solve(int rt,int d) {
    int u=num[d].FR,v=num[d].SE;int sz=0;for(int i=0;i<vt2[d].size();i++) {
    val[++sz]=vt2[d][i].FR;vt3[vt2[d][i].FR].push_back(vt2[d][i].SE);}sort(val+1,val+sz+1,cmp);int top=0;st[++top]=u;for(int i=1;i<=sz;i++)if (val[i]!=st[top]) {
    int x=val[i],p=lca(x,st[top]);for(;;) {
    if (dep[p]<=dep[st[top-1]]) {
    ee[st[top-1]].push_back(st[top]);top--;}else if (dep[p]<dep[st[top]]) {
    ee[p].push_back(st[top]);st[top]=p;}else break;}if (st[top]!=x) st[++top]=x;}for(;top>1;top--) ee[st[top-1]].push_back(st[top]);dfs3(u,u,1,rt);for(int i=0;i<vt4[u].size();i++) tr[1].add(dfn[vt4[u][i]],n,-1);vector<int>().swap(vt4[u]);
}void dfs2(int x) {
    for(int i=0;i<e[x].size();i++)if (e[x][i]!=fa[x][0]) {
    int u=e[x][i];dfs2(u);root[x]=SGT::merge(1,n,root[x],root[u]);}for(int i=0;i<vt1[x].size();i++) root[x]=SGT::update(1,n,root[x],dfn[vt1[x][i]]);ll s=0;int sz=0;for(int i=0;i<q[x].size();i++) {
    int u=q[x][i].FR,v=q[x][i].SE;int t1=((u==x)?x:jump(u,dep[u]-dep[x]-1)),t2=((v==x)?x:jump(v,dep[v]-dep[x]-1));if (dep[u]-dep[x]>=k) {
    int rt=root[jump(u,dep[u]-dep[x]-k)];ans+=SGT::query(1,n,rt,1,n)-SGT::query(1,n,rt,dfn[x],ed[x]);s+=SGT::query(1,n,rt,dfn[x],ed[x]);if (t1!=x) s-=SGT::query(1,n,rt,dfn[t1],ed[t1]);if (t2!=x) s-=SGT::query(1,n,rt,dfn[t2],ed[t2]);if (v==x) s--;}if (dep[v]-dep[x]>=k) {
    int rt=root[jump(v,dep[v]-dep[x]-k)];ans+=SGT::query(1,n,rt,1,n)-SGT::query(1,n,rt,dfn[x],ed[x]);s+=SGT::query(1,n,rt,dfn[x],ed[x]);if (t1!=x) s-=SGT::query(1,n,rt,dfn[t1],ed[t1]);if (t2!=x) s-=SGT::query(1,n,rt,dfn[t2],ed[t2]);if (u==x) s--;}if (u!=x&&v!=x) {
    if (!mp.count(pr(t1,t2))) {
    mp[pr(t1,t2)]=++sz;num[sz]=pr(t1,t2);}vt2[mp[pr(t1,t2)]].push_back(pr(u,v));}}ans+=(s>>1);for(int i=1;i<=sz;i++)solve(x,i);for(int i=1;i<=sz;i++) vector<pr>().swap(vt2[i]);mp.clear();sz=0;
}int main() {
    int m;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}dfs1(1);for(int i=1;i<=m;i++) {
    int x,y;scanf("%d%d",&x,&y);if (dfn[x]>dfn[y]) swap(x,y);q[lca(x,y)].push_back(pr(x,y));vt1[x].push_back(y);vt1[y].push_back(x);}dfs2(1);printf("%lld\n",ans);return 0;
}
/* 5 3 2 1 2 2 3 1 4 4 5 1 4 2 5 4 3 */