F. Strange Memory

呜呜呜，想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ，之后发现其实根本没有好的处理方法，只能拆位计算贡献。

考虑第 $B$ 位的贡献，那么一个点 $x$ 就有两个属性 $a_x$ 和x>>B&1，这样就可以Dsu on tree统计了。

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxa=1<<20;

int n,a[maxn+5],sum[maxa+5][2],si[maxn+5],SH[maxn+5],B;LL cnt,ans;
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void DFS(int x,int pre=0){
    si[x]=1;
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre){
            DFS(son[j],x);si[x]+=si[son[j]];
            if (si[son[j]]>si[SH[x]]) SH[x]=son[j];
        }
}
void Count(int x,int w,int pre=0){
    cnt+=sum[a[x]^w][x>>B&1^1];
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre) Count(son[j],w,x);
}
void Update(int x,int f,int pre=0){
    sum[a[x]][x>>B&1]+=f;
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre) Update(son[j],f,x);
}
void Solve(int x,int pre=0,bool fl=false){
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre && son[j]!=SH[x]) Solve(son[j],x,false);
    if (SH[x]) Solve(SH[x],x,true);
    sum[a[x]][x>>B&1]++;
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre && son[j]!=SH[x])
            Count(son[j],a[x],x),Update(son[j],1,x);
    if (!fl) Update(x,-1,pre);
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    DFS(1);for (B=0;B<17;B++) cnt=0,Solve(1),ans+=cnt*(1<<B);
    printf("%lld\n",ans);return 0;
}

J. Abstract Painting

其实就是选不相交线段的方案数，由于线段长度很小，因此考虑状压DP：$f_{i,s}$ 表示放完左端点在 $i$ 的线段之后，$i$ 的后 $10$ 位右端点状态为 $s$ 的方案数（ $1$ 表示该位置上放了右端点）。

放长度为 $d$ 的线段时，如果 $i$ 到 $i+d$ 之间已经有了右端点，那么就不能放下这条线段。每次转移时枚举选了 $2,4,6,8,10$ 中哪些线段。

而初始时给出的线段其实就是强制选，只要在转移的时候强制加上就行了。

复杂度 $O(n2^{10}2^{5}+2^{10}k)$ 。

#include<cstdio>
using namespace std;
const int maxn=1000,maxk=5000,maxs=1<<10,MOD=1e9+7;

int n,K,f[maxn+5][maxs],c[15];bool pre[15],vis[maxn+5][15];
int E,lnk[maxn+5],nxt[maxk+5],son[maxk+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
bool check(int i,int s){
    pre[0]=false;for (int i=0;i<10;i++) pre[i+1]=pre[i] || (s>>i&1);
    for (int j=lnk[i];j;j=nxt[j]) if (pre[son[j]-i-1]) return false;
    return true;
}
int main(){
    scanf("%d%d",&n,&K);
    for (int i=1,x,r,L,R;i<=K;i++) scanf("%d%d",&x,&r),L=x-r,R=x+r,Add(L,R),vis[L][R-L]=true;
    f[0][0]=1;
    for (int i=0;i<n;i++)
        for (int s=0;s<(1<<10);s++)
            if (f[i][s] && check(i,s)){
                pre[0]=false;for (int i=0;i<10;i++) pre[i+1]=pre[i] || (s>>i&1);
                int m=0;for (int d=2;d<=10 && i+d<=n && !pre[d-1];d+=2) c[m++]=d;
                for (int C=0;C<(1<<m);C++){
                    int t=s>>1;for (int j=0;j<m;j++) if (C>>j&1) t|=1<<c[j]-2;
                    for (int j=0;j<m;j++) if ((C>>j&1^1) && vis[i][c[j]]) goto GG;
                    f[i+1][t]=(f[i+1][t]+f[i][s])%MOD;GG:;
                }
            }
    printf("%d\n",f[n][0]);return 0;
}