如题。

更好的阅读体验

ZJOI2020 Day1

T1

字符串菜鸡爬了爬了

但是我是怎么拿到 10 分的好成绩的啊哈希都不会打吗

日常怀疑自己是怎么拿到THU1=的（1/1）

T2

题目链接

考虑以下 5 类点：

白色点标记会被清空；红色点一定会被打上标记；灰色点标记一定不变；黄色点标记也不变。橙色点比较麻烦，它取决于自己的祖先有没有标记 pushdown 下来。

设 f_x 是当前 x 有标记的概率，g_x 是 x 的祖先中有标记的概率。于是就可以 DP 了。

我们发现每次转移系数都一样，于是矩乘即可。

考场上 f 讨论了巨久，然后一直没想到设个 g 出来……讲道理如果没做过去年那题这题可能确实没那么好做，可是谁叫整个考场只有我这个sb没做过那题呢

日常怀疑自己是怎么拿到THU1=的（2/1）

#include<bits/stdc++.h>
using namespace std;

const int p=998244353;

struct mat{
    int a[3][3];
    mat (){memset(a,0,sizeof(a));}
    mat operator *(const mat b)const{
        mat c;
        for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
            c.a[i][k]=(c.a[i][k]+1LL*a[i][j]*b.a[j][k]%p)%p;
        return c;
    }
    mat qpow(int k){
        mat c,b=*this;
        for(int i=0;i<3;i++) c.a[i][i]=1;
        while(k){
            if(k&1) c=c*b;
            b=b*b;
            k>>=1;
        }
        return c;
    }
}G,H;

int N,K,M;
int A[400005],lc[400005],rc[400005],Lp[400005],midp[400005],Rp[400005],idx,y;
int init(int L,int R){
    int x=++idx;Lp[x]=L,Rp[x]=R;
    int ty;
    if(L!=R) ty=++y,lc[x]=init(L,A[ty]),rc[x]=init(A[ty]+1,R),midp[x]=A[ty];
    return x;
}

int calc(int l){return 1LL*l*(l+1)/2%p;}
int calc(int l,int r){return (calc(r)-calc(l-1)+p)%p;}
int qpow(int a,int k){
    int ans=1;
    while(k){
        if(k&1) ans=1LL*ans*a%p;
        a=1LL*a*a%p;
        k>>=1;
    }
    return ans;
}

int ans;
int h[400005],f[400005],s[400005],g[400005];
void Solve(int x,int fa){
    G=mat();
    int L=Lp[x],R=Rp[x];
    f[x]=(1ll*L*(N+1-R)%p*M%p-s[fa]+p)%p;
    s[x]=(s[fa]+f[x])%p;
    h[x]=1ll*(calc(L-1)+calc(N-R))*M%p;
    int p1=f[x],
        p2=s[fa],
        p3=g[x],
        p4=(1ll*(R-L)*(N-R+L-1)+calc(R-L+1)-1)%p*M%p,
        p5=h[fa];
    G.a[0][0]=((p3+p4)%p+p5)%p, G.a[0][1]=p2,           G.a[0][2]=p1;
    G.a[1][0]=p4,           G.a[1][1]=(p2+p5)%p,    G.a[1][2]=(p1+p3)%p;
    G.a[2][0]=p4,           G.a[2][1]=0,            G.a[2][2]=((p1+p2)%p+(p3+p5)%p)%p;
    H=G.qpow(K);ans=(ans+H.a[0][2])%p;
    if(L==R)return;
    g[lc[x]]=(1ll*(R-midp[x])*(N-R)+calc(R-midp[x]))%p*M%p;
    g[rc[x]]=(1ll*(midp[x]-L+1)*(L-1)+calc(midp[x]-L+1))%p*M%p;
    Solve(lc[x],x);Solve(rc[x],x);
}

int main(){
    scanf("%d%d",&N,&K);M=qpow(calc(N),p-2);
    for(int i=1;i<N;i++) scanf("%d",&A[i]);
    init(1,N);Solve(1,0);
    printf("%d\n",ans);
}

T3

题目链接

首先我们都知道如果只有 1 操作答案就是

\sum\max(A_i-A_{i-1},0)

那么我们考虑对每个元素，其中的 x_i 用 1 操作覆盖，A_i-x_i 用 23 操作覆盖

于是我们需要最小化

\sum\max(x_i-x_{i-1},0)+\sum\max(A_i-x_i-A_{i-2}+x_{i-2},0)

那么很明显这是一个线性规划问题：

\begin{cases}x_i,y_i,z_i&\ge 0\\-x_i&\ge -A_i\\y_i-x_i+x_{i-1}&\ge 0\\z_i+x_i-x_{i-2}&\ge A_i-A_{i-2}\end{cases} \text{最小化}\sum y_i+\sum z_i

这东西看起来显然没法做，要是看起来就有办法做那就不会是 ZJOID1T3 了。对偶一下：

AX\ge B\rightarrow A^TY\le C \begin{cases}u_i,v_i,w_i&\ge 0\\-u_i-v_i+v_{i+1}+w_i-w_{i+2}&\le 0\\v_i&\le 1\\w_i&\le 1\end{cases} \text{最大化}\sum -A_iu_i+\sum(A_i-A_{i-2})w_i

显然 u_i 直接取 \max(-v_i+v_{i+1}+w_i-w_{i+2},0) 即可。这是个幺模矩阵，所以可以当自变量只能取整数做，所以 v,w 只能取 0,1，大力状压即可。

明明是一个问题的两种表述为什么一种比另一种好算呢，人类的计算机科学就是逊啦（1/1）

熟悉线性规划的大爷可能可以光速切？考前刚学了单纯形法然后拿了10分的我可能是个nt

日常怀疑自己是怎么拿到THU1=的（3/1）

反正膜明哥就是了

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int T,N,A[100005]; 
ll F[8],tmp[8];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&A[i]);
        memset(F,192,sizeof(F));F[0]=0;
        for(int i=N;i;i--){
            memset(tmp,192,sizeof(tmp));
            for(int s=0;s<8;s++){
                int v1=s&1,w1=(s&2)>>1,w2=(s&4)>>2;
                ll val=A[i]-(i>2?A[i-2]:0);
                for(int v0=0;v0<2;v0++)
                for(int w0=0;w0<2;w0++)
                    tmp[v0|(w0<<1)|(w1<<2)]=max(tmp[v0|(w0<<1)|(w1<<2)],F[s]+val*w0-1LL*max(-v0+v1+w0-w2,0)*A[i]);
            }
            swap(tmp,F);
        }
        ll ans=-(1LL<<60); 
        for(int s=0;s<8;s++) ans=max(ans,F[s]);
        printf("%lld\n",ans);
    }
}

ZJOI2020 Day2

T1

神必题，这题超级没有素质，连个题解都搜不到

膜全场严格最高分神仙 hhz

T2

题目链接

想不到吧全场最可做的三题两道是数数

想不到吧能找到题解的四题两道是数数

想不到吧你这题拿的分数比其他所有题加起来还多

想不到吧你因为 T3 没建文件夹神必爆 0 了，你可能会想 T3 不建文件夹怎么会导致前两题爆 0，但事实就是这样小编也很惊讶

min-max 容斥线

int clk=clock();

首先 min-max 容斥一下，答案就变为

\sum_{s}(-1)^{|s|-1}\text{E}\max(s) $$\text{cnt}(s)=\left|\bigcup_{i\in s}a_i\right|$$ 抽卡次数期望就是 $n\sum_{i=1}^{\text{cnt}(s)}\frac{1}{i}$。我们尝试求出 $\text{cnt}$ 为某个值的集合的权值（$(-1)^{|s|-1}$）和。 显然如果有两段不连续的干员段，那么我们直接多项式卷积就可以了，每次合并两个最短的多项式，这一部分是 $O(n\log^2 n)$ 的。 那么考虑计算某一个长度为 $n$ 的段，我们有一个 DP $$f_{i,j}=-\sum_{k=1}^K f_{i-k,j-k}-\sum_{i'=0}^{i-K-1} f_{i',j-k}$$ 前缀和优化这个 DP 你就可以获得 $70$ 分的好成绩。 那么我们可以写出 $$F=1-(xy\dfrac{1-(xy)^K}{1-xy}+x^{K+1}y^K\dfrac{1}{1-x})F$$ 这玩意是完全没法解的，也就是说这个 min-max 容斥完全是把你往坑里带的，你浪费了你生命中宝贵的 ``((double)clock()-clk)/CLOCKS_PER_SECOND`` 秒。 ### 正解线 考虑 sb 状压中，new 干员数量一步一步 +1 到结束的过程。称抽出了一个幻神阵容的状态为合法的。 一个共抽出了 $i$ 个 new 干员的非法状态在一条完整的路线中被经过的概率显然就是 $\dfrac{1}{m\choose i}$，而它到下一个状态的期望时间显然是 $\dfrac{m}{m-i}$。 因为一旦合法抽卡就立即结束了，所以我们要求的就是所有非法状态被经过的概率和它的期望贡献（到下一个状态的期望时间）。也就是要求大小为 $i$ 的非法状态数。 还是可以分别对连续段计算。下面考虑单个长度为 $n$ 的连续段。 考虑每次加连续的一段 $1$ 和一个 $0$，第 $n+1$ 强制选 $0$，那么大小为 $m$ 的答案就是 $$[x^{n+1}]\left(\sum_{i=1}^{K}x^i\right)^m$$ 写成生成函数就是（其中 $G(x)=x\dfrac{1-x^K}{1-x}$） $$[x^{n+1}]\dfrac{1}{1-yG(x)}$$ 写成生成函数有什么用呢，看起来还没之前那个好算啊。不好算没关系，（拉格朗日）反演一下就好算了： $$[x^{n+1}]\dfrac{1}{1-yG(x)}=\dfrac{1}{n+1}[x^{-1}]\dfrac{1}{(1-yx)^2}\cdot\dfrac{1}{G^{\left<-1\right>(n+1)}(x)}$$ 明明是一个问题的两种表述为什么一种比另一种好算呢，人类的计算机科学就是逊啦（2/1） $F=G^{\left<-1\right>}$ 显然可以牛迭： $$F\dfrac{1-F^K}{1-F}=x$$ $$-x+(1+x)F-F^{K+1}=0$$ 求导一下是 $$1+x-(K+1)F^K$$ 那么这题就做完了。 代码如下，格式化后 230 行： ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; const int p=998244353,maxN=262144*2,g=3,ig=332748118,inv2=(p+1)/2; int W[maxN],iW[maxN]; int fac[maxN],ifac[maxN],inv[maxN]; int qpow(int a,int k){ int ans=1; while(k){ if(k&1) ans=1LL*ans*a%p; a=1LL*a*a%p; k>>=1; } return ans; } void inline check(int &x){x-=p,x+=x>>31&p;} void init(){ int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN); W[0]=iW[0]=1; for(int i=1;i<maxN;i++) W[i]=1LL*W[i-1]*w%p, iW[i]=1LL*iW[i-1]*iw%p; fac[0]=ifac[0]=fac[1]=ifac[1]=inv[1]=1; for(int i=2;i<maxN;i++) fac[i]=1LL*fac[i-1]*i%p, inv[i]=1LL*(p-p/i)*inv[p%i]%p, ifac[i]=1LL*ifac[i-1]*inv[i]%p; } int R[maxN]; void NTT(int d[],bool flg,int n0){ int x=1,len=0;while(x<n0) x<<=1,len++; for(int i=0;i<x;i++){ R[i]=(R[i>>1]>>1)|((i&1)<<(len-1)); if(i<R[i]) swap(d[i],d[R[i]]); } for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1) for(int j=0;j<x;j+=(i<<1)) for(int k=0,u=0;k<i;k++,u+=l){ int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p; check(d[j|k]=a0+a1);check(d[j|i|k]=a0-a1+p); } if(flg){ int invx=qpow(x,p-2); for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p; } } int tmpans[maxN+5],tmpd[maxN+5]; void Inv(int d[],int ans[],int n0){ if(n0==1){ans[0]=qpow(d[0],p-2);return;} Inv(d,ans,n0>>1); for(int i=0;i<n0;i++) tmpans[i]=ans[i],tmpd[i]=d[i]; NTT(tmpans,0,n0<<1);NTT(tmpd,0,n0<<1); for(int i=0;i<(n0<<1);i++) tmpans[i]=1LL*tmpans[i]*tmpans[i]%p*tmpd[i]%p; NTT(tmpans,1,n0<<1); for(int i=0;i<n0;i++) check(ans[i]+=ans[i]),check(ans[i]+=-tmpans[i]+p); for(int i=0;i<(n0<<1);i++) tmpans[i]=tmpd[i]=0; } void Der(int d[],int ans[],int n0){ for(int i=0;i<n0;i++) ans[i]=1LL*d[i+1]*(i+1)%p; } void Int(int d[],int ans[],int n0){ for(int i=n0-1;i>=0;i--) ans[i+1]=1LL*d[i]*inv[i+1]%p;ans[0]=0; } int derd[maxN+5],invd[maxN+5]; void Ln(int d[],int ans[],int n0){ Der(d,derd,n0);Inv(d,invd,n0); NTT(derd,0,n0<<1);NTT(invd,0,n0<<1); for(int i=0;i<(n0<<1);i++) derd[i]=1LL*derd[i]*invd[i]%p; NTT(derd,1,n0<<1);Int(derd,ans,n0); for(int i=0;i<(n0<<1);i++) derd[i]=invd[i]=0; } int lnans[maxN+5]; void Exp(int d[],int ans[],int n0){ if(n0==1){ans[0]=1;return;} Exp(d,ans,n0>>1); Ln(ans,lnans,n0); for(int i=0;i<n0;i++) check(lnans[i]=d[i]-lnans[i]+p);for(int i=n0;i<(n0<<1);i++) lnans[i]=ans[i]=0; lnans[0]=(lnans[0]+1)%p; NTT(lnans,0,n0<<1);NTT(ans,0,n0<<1); for(int i=0;i<(n0<<1);i++) ans[i]=1LL*ans[i]*lnans[i]%p; NTT(ans,1,n0<<1); for(int i=0;i<n0;i++) lnans[i]=0; for(int i=n0;i<(n0<<1);i++) ans[i]=lnans[i]=0; } int tmppow[maxN+5],tmppow2[maxN+5]; void Pow(int d[],int ans[],int n0,int k){ int pos=-1,a0; for(int i=0;i<n0;i++) if(d[i]!=0){pos=i;break;} if(pos==-1) return;a0=qpow(d[pos],p-2); for(int i=0;i<n0-pos;i++) tmppow[i]=1LL*d[i+pos]*a0%p;for(int i=n0-pos;i<n0;i++) tmppow[i]=0; for(int i=0;i<n0;i++) tmppow2[i]=0; Ln(tmppow,tmppow2,n0);for(int i=0;i<n0;i++) tmppow2[i]=1LL*tmppow2[i]*k%p; Exp(tmppow2,ans,n0);a0=qpow(d[pos],k); for(int i=n0-1;i>=1LL*k*pos;i--) ans[i]=1LL*ans[i-1LL*k*pos]*a0%p; for(int i=min(1LL*k*pos-1,(ll)n0-1);i>=0;i--) ans[i]=0; } int convtmp1[maxN+5],convtmp2[maxN+5]; void Conv(int d1[],int d2[],int ans[],int n0){ for(int i=0;i<n0;i++) convtmp1[i]=d1[i],convtmp2[i]=d2[i]; NTT(convtmp1,0,n0); NTT(convtmp2,0,n0); for(int i=0;i<n0;i++) ans[i]=1LL*convtmp1[i]*convtmp2[i]%p; NTT(ans,1,n0); } int convans[maxN+5]; vector<int> Conv(vector<int> d1,vector<int> d2,int n0){ for(int i=0;i<n0;i++) convtmp1[i]=convtmp2[i]=0; for(int i=0;i<d1.size();i++) convtmp1[i]=d1[i]; for(int i=0;i<d2.size();i++) convtmp2[i]=d2[i]; NTT(convtmp1,0,n0); NTT(convtmp2,0,n0); for(int i=0;i<n0;i++) convans[i]=1LL*convtmp1[i]*convtmp2[i]%p; NTT(convans,1,n0); vector<int> ans; for(int i=0;i<n0;i++) ans.push_back(convans[i]); return ans; } int N,K; int Aans[maxN+5],A_ans[maxN+5],iA_ans[maxN+5]; void Solve(int ans[],int n0){ if(n0==2){ans[0]=0;ans[1]=1;return;} Solve(ans,n0>>1); for(int i=0;i<n0;i++) Aans[i]=A_ans[i]=iA_ans[i]=0; Pow(ans,A_ans,n0,K);Conv(A_ans,ans,Aans,(n0<<1)); for(int i=n0;i<(n0<<1);i++) Aans[i]=0;Aans[1]++; for(int i=0;i<n0;i++) Aans[i]=(p-Aans[i])%p; for(int i=0;i<(n0>>1)+1;i++) Aans[i]=((ll)Aans[i]+ans[i]+(i?ans[i-1]:0))%p; for(int i=0;i<n0;i++) A_ans[i]=(p-1LL*A_ans[i]*(K+1)%p)%p; A_ans[0]++;A_ans[1]++;Inv(A_ans,iA_ans,n0); Conv(Aans,iA_ans,Aans,n0<<1);for(int i=n0;i<(n0<<1);i++) Aans[i]=0; for(int i=0;i<n0;i++) ans[i]=(ans[i]-Aans[i]+p)%p; } int F[maxN]; int A[maxN]; int B[maxN],len,maxB,n0; struct cmp{ bool operator ()(const vector<int> &cmpa,const vector<int> &cmpb) {return cmpa.size()>cmpb.size();} }; int tmpF[maxN]; int main(){ // freopen("straight8.in","r",stdin); init(); scanf("%d%d",&N,&K); for(int i=1;i<=N;i++) scanf("%d",&A[i]);sort(A+1,A+N+1); for(int i=1,lst=-1;i<=N;lst=A[i],i++) if(A[i]!=lst+1) B[++len]=1;else B[len]++; for(int i=1;i<=len;i++) maxB=max(maxB,B[i]); sort(B+1,B+len+1); n0=1;while(n0<maxB+2) n0<<=1; // int clk=clock(); Solve(F,n0); // printf("%d\n",clock()-clk); for(int i=0;i<n0-1;i++) F[i]=F[i+1];F[n0-1]=0; priority_queue<vector<int>,vector<vector<int> >,cmp > Q; vector<int> lstC; for(int i=1;i<=len;i++){ if(B[i]==B[i-1]){Q.push(lstC);continue;} int n1=1;while(n1<B[i]+1) n1<<=1; for(int j=0;j<n1;j++) tmpF[j]=0; Pow(F,tmpF,n1,p-(B[i]+1)); vector<int> C; for(int j=0,invB=qpow(B[i]+1,p-2);j<=B[i];j++) C.push_back(1LL*(B[i]-j+1)*tmpF[j]%p*invB%p); Q.push(lstC=C); } while(Q.size()!=1){ vector<int> C1=Q.top();Q.pop(); vector<int> C2=Q.top();Q.pop(); int n1=1;while(n1<C1.size()+C2.size()) n1<<=1; Q.push(Conv(C1,C2,n1)); } int ans=0;vector<int> ANS=Q.top(); for(int i=0;i<ANS.size();i++) ans=(ans+1LL*ANS[i]*fac[i]%p*fac[N-i]%p*ifac[N]%p*N%p*qpow(N-i,p-2)%p)%p; printf("%d\n",ans); } ``` ## T3 神必题，这题超级没有素质，连个题解都搜不到 # 联考 A 卷 Day1 ## T1 傻逼题懒得写了 ## T2 [题目链接](https://www.luogu.com.cn/problem/P6620) 组合数和幂很不搭，考虑把 $f$ 转成下降幂： $$f(k)=\sum_{i=0}^m b_ik^{\underline i}$$ 那么答案就是 $$\sum_{d=0}^mb_d\sum_{k=d}^n\dfrac{n!}{(n-k)!(k-d)!}x^k$$ $$\sum_{d=0}^mb_d\sum_{k=d}^n\dfrac{n!(n-d)!}{(n-k)!(k-d)!(n-d)!}x^k$$ $$\sum_{d=0}^mb_d\sum_{k=d}^n{n-d\choose k-d}n^{\underline d}x^k$$ 如果你认真读过水泥数学或者研究过下降幂，这个东西还是比较容易想到的。~~而我不是这种人~~ 枚举改为 $k-d$。整理一下。 $$\sum_{d=0}^mb_dn^{\underline d}x^d\sum_{k=0}^{n-d}{n-d\choose k}x^k$$ $$\sum_{d=0}^mb_dn^{\underline d}x^d(1+x)^{n-d}$$ N 方暴力转下降幂即可。 ## T3 保序回归是啥啊不会啊qaq # 联考 A 卷 Day2 做完后最大的感悟是： 何苦生在浙江…… ## T1 [题目链接](https://www.luogu.com.cn/problem/P6622) 带水题。状压，答案贡献分别摊到两个点上： 考虑安排好 $1...x-1$，然后在坐标为 $x$ 处放一个点 $u$。考虑另一个点 $v$。贡献为 $$\begin{cases}x\cdot\text{cnt}(v\in s,(v,u))\\kx\cdot\text{cnt}(v\notin s,(v,u))\\kx\cdot\text{cnt}(v\in s,(u,v))\\-x\cdot\text{cnt}(v\notin s,(u,v))\end{cases}$$ 看似要枚举 $u,v$ 实则不然。考虑对于每个 $u$ 暴力维护这 4 个 $\text{cnt}$，每次 $s$ 有二进制位变动时修改贡献。显然 $s$ 的二进制位只会变动 $O(2^{m})$ 次。 就这？就这？就这？就这？ 和 ZJOID2T1 一比，高下立分啊…… ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; int N,M,K; int siz[1<<23]; int cnt[23][4]; int G[23][23]; void Inc(int v){ for(int u=0;u<M;u++) cnt[u][0]+=G[v][u],cnt[u][1]-=G[v][u], cnt[u][2]+=G[u][v],cnt[u][3]-=G[u][v]; } void Dec(int v){ for(int u=0;u<M;u++) cnt[u][0]-=G[v][u],cnt[u][1]+=G[v][u], cnt[u][2]-=G[u][v],cnt[u][3]+=G[u][v]; } ll Calc(int u,int x){ return x*(cnt[u][0]+K*cnt[u][1]+K*cnt[u][2]-cnt[u][3]); } ll F[1<<23]; int main(){ scanf("%d%d%d",&N,&M,&K); int lst;scanf("%d",&lst);lst--; for(int i=2;i<=N;i++){ int s;scanf("%d",&s);s--; if(lst!=s) G[lst][s]++; lst=s; } for(int v=0;v<M;v++) for(int u=0;u<M;u++) cnt[u][1]+=G[v][u],cnt[u][3]+=G[u][v]; memset(F,63,sizeof(F));F[0]=0; for(int s=0;s<(1<<M);s++){ siz[s]=siz[s>>1]+(s&1); int x=siz[s]+1; for(int u=0;u<M;u++) if(!((s>>u)&1)) F[s|(1<<u)]=min(F[s|(1<<u)],F[s]+Calc(u,x)); for(int u=0;;u++) if(!((s>>u)&1)){Inc(u);break;} else Dec(u); } printf("%lld\n",F[(1<<M)-1]); } ``` ## T2 [题目链接](https://www.luogu.com.cn/problem/P6623) 考虑第 $k$ 位。考虑一个节点对它父亲的贡献。显然当往上走的时候贡献会在 $00...011...1$ 中循环。看样子可以树上差分？可惜是 $O(N^2)$ 的。 考虑在 $k$ 很小的时候这个做法非常浪费，注意到 $dep_i$ 模 $2^{k}$ 同余的节点被差分到的是一样的，然后就做完了。 就这？就这？就这？就这？ 和 ZJOID2T2 一比，高下立分啊…… ```cpp #include<bits/stdc++.h> using namespace std; int N; int V[550000]; vector<int> G[550000]; int C[21][1048576]; int dep[550000]; long long ANS; int Solve(int x){ int ans=V[x]; for(int k=0;k<=20;k++) C[k][(dep[x]+V[x])&((1<<k)-1)]^=(1<<k); for(int k=0;k<=20;k++) ans^=C[k][dep[x]&((1<<k)-1)]; for(auto v:G[x]){ dep[v]=dep[x]+1; ans^=Solve(v); } for(int k=0;k<=20;k++) ans^=C[k][dep[x]&((1<<k)-1)]; ANS+=ans; return ans; } int main(){ scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&V[i]); for(int i=2;i<=N;i++){ int p;scanf("%d",&p); G[p].push_back(i); } Solve(1); printf("%lld\n",ANS); } ``` ## T3 [题目链接](https://www.luogu.com.cn/problem/P6624) 首先必然可以反演，然后就变成[这题](https://www.luogu.com.cn/problem/P5296)究极弱化版了。注意可以只选择能使图联通的边集跑行列式。 兄啊 D2T3 怎么放的是一道 sb 二合一啊 就这？就这？就这？就这？ 和 ZJOID2T3 一比，高下立分啊…… ```cpp #include<bits/stdc++.h> using namespace std; int N,M; const int tt=998244353; int fac[35],inv[35],ifac[35]; bool flg[160000];int pri[160000],cnt,phi[160000]; void init(){ inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1; for(int i=2;i<=30;i++) inv[i]=1LL*(tt-tt/i)*inv[tt%i]%tt, fac[i]=1LL*fac[i-1]*i%tt, ifac[i]=1LL*ifac[i-1]*inv[i]%tt; phi[1]=1; for(int i=2;i<=152501;i++){ if(!flg[i]) phi[i]=i-1,pri[++cnt]=i; for(int j=1;j<=cnt&&i*pri[j]<=152501;j++){ flg[i*pri[j]]=1; if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;} else phi[i*pri[j]]=phi[i]*phi[pri[j]]; } } } int qpow(int a,int k){ int ans=1; while(k){ if(k&1) ans=1LL*ans*a%tt; a=1LL*a*a%tt; k>>=1; } return ans; } struct tni{ int a[2]; tni (){memset(a,0,sizeof(a));} tni (int b){ for(int i=0,mul=1;i<=1;i++,mul=1LL*mul*b%tt) a[i]=1LL*ifac[i]*mul%tt; } bool any(){ for(int i=0;i<=1;i++) if(a[i]) return 1; return 0; } tni operator +(const tni b)const{ tni c; for(int i=0;i<=1;i++) c.a[i]=(a[i]+b.a[i])%tt; return c; } tni operator -(const tni b)const{ tni c; for(int i=0;i<=1;i++) c.a[i]=(a[i]-b.a[i]+tt)%tt; return c; } tni operator *(const int b)const{ tni c; for(int i=0;i<=1;i++) c.a[i]=1LL*a[i]*b%tt; return c; } tni operator *(const tni b)const{ tni c; for(int i=0;i<=1;i++) for(int j=0;i+j<=1;j++) c.a[i+j]=(c.a[i+j]+1LL*a[i]*b.a[j]%tt)%tt; return c; } tni inv(){ tni c; c.a[0]=qpow(a[0],tt-2); for(int i=1;i<=1;i++){ for(int j=0;j<i;j++) c.a[i]=(c.a[i]-1LL*c.a[j]*a[i-j]%tt+tt)%tt; c.a[i]=1LL*c.a[i]*c.a[0]%tt; } return c; } void outp(){ for(int i=0;i<=1;i++) printf("%d ",a[i]);printf("\n"); } }; struct mat{ int n,m; tni a[35][35]; void Gauss(int p,int &flg){ if(p==n) return; for(int i=p+1;i<=m;i++){ tni tmp=a[i][p]*(a[p][p].inv()); for(int j=p;j<=m;j++) a[i][j]=a[i][j]-a[p][j]*tmp; } Gauss(p+1,flg); } tni Det(){ int flg=0;tni ANS(0); Gauss(1,flg); for(int i=1;i<=n;i++) ANS=ANS*a[i][i]; return ((flg&1)^(n&1))?tni()-ANS:ANS; } }G; struct Edge{ int u,v,c; }H[1005]; int fa[35]; int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));} int Solve(int d){ for(int i=1;i<=N;i++) fa[i]=i;int tot=N; for(int i=1;i<=M;i++)if(H[i].c%d==0) if(find(H[i].u)!=find(H[i].v)) fa[find(H[i].u)]=find(H[i].v),tot--; if(tot!=1) return 0; G.n=G.m=N-1; for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) G.a[i][j].a[0]=0,G.a[i][j].a[1]=0; for(int i=1;i<=M;i++)if(H[i].c%d==0){ tni tmp(H[i].c); int u=H[i].u,v=H[i].v; G.a[u][v]=G.a[v][u]=tmp; G.a[u][u]=G.a[u][u]-tmp; G.a[v][v]=G.a[v][v]-tmp; } tni ans=G.Det(); return 1LL*ans.a[1]*fac[1]%tt; } int main(){ init(); scanf("%d%d",&N,&M); for(int i=1;i<=M;i++) scanf("%d%d%d",&H[i].u,&H[i].v,&H[i].c); int ans=0; for(int d=1;d<=152501;d++) ans=(ans+1LL*phi[d]*Solve(d)%tt)%tt; printf("%d\n",ans); } ```