0%

省选 2020 补题记录

如题。

目前进度:

T1代码 T1题解 T2代码 T2题解 T3代码 T3题解
ZJOI2020 Day1 $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$
ZJOI2020 Day2 $\color{red}\text{unsolvable}$ $\color{red}\text{unsolvable}$ $\sqrt{}$ $\sqrt{}$ $\color{red}\text{unsolvable}$ $\color{red}\text{unsolvable}$
联考 A 卷 Day1 $\text{skipped}$ $\text{skipped}$ $\sqrt{}$ $\sqrt{}$
联考 A 卷 Day2 $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$

ZJOI2020 Day1

T1

字符串菜鸡爬了爬了

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

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

T2

题目链接

考虑以下 5 类点:

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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 操作答案就是

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

于是我们需要最小化

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

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

显然 $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)

反正膜明哥就是了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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 容斥一下,答案就变为

$\max(s)$ 就是说 $s$ 中的所有阵容中的每一个干员都被抽出来,设 $a_i$ 是第 $i$ 组幻神阵容,那么要抽的干员数就是

抽卡次数期望就是 $n\sum_{i=1}^{\text{cnt}(s)}\frac{1}{i}$。我们尝试求出 $\text{cnt}$ 为某个值的集合的权值($(-1)^{|s|-1}$)和。

显然如果有两段不连续的干员段,那么我们直接多项式卷积就可以了,每次合并两个最短的多项式,这一部分是 $O(n\log^2 n)$ 的。

那么考虑计算某一个长度为 $n$ 的段,我们有一个 DP

前缀和优化这个 DP 你就可以获得 $70$ 分的好成绩。

那么我们可以写出

这玩意是完全没法解的,也就是说这个 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$ 的答案就是

写成生成函数就是(其中 $G(x)=x\dfrac{1-x^K}{1-x}$)

写成生成函数有什么用呢,看起来还没之前那个好算啊,还有一个恶心的复合。不好算没关系,(拉格朗日)反演一下就好算了:

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

很草的是 P6633 的所有题解都在等式的右边漏了一个 $y$,众所周知做数数题的最好办法就是抄 EI。

$F=G^{\left<-1\right>}$ 显然可以牛迭:

求导一下是

那么这题就做完了。

代码如下,格式化后 230 行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#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

题目链接

组合数和幂很不搭,考虑把 $f$ 转成下降幂:

那么答案就是

如果你认真读过水泥数学或者研究过下降幂,这个东西还是比较容易想到的。而我不是这种人

枚举改为 $k-d$。整理一下。

N 方暴力转下降幂即可。

T3

保序回归是啥啊不会啊qaq

联考 A 卷 Day2

做完后最大的感悟是:

何苦生在浙江……

T1

题目链接

带水题。状压,答案贡献分别摊到两个点上:

考虑安排好 $1…x-1$,然后在坐标为 $x$ 处放一个点 $u$。考虑另一个点 $v$。贡献为

看似要枚举 $u,v$ 实则不然。考虑对于每个 $u$ 暴力维护这 4 个 $\text{cnt}$,每次 $s$ 有二进制位变动时修改贡献。显然 $s$ 的二进制位只会变动 $O(2^{m})$ 次。

就这?就这?就这?就这?

和 ZJOID2T1 一比,高下立分啊……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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

题目链接

考虑第 $k$ 位。考虑一个节点对它父亲的贡献。显然当往上走的时候贡献会在 $00…011…1$ 中循环。看样子可以树上差分?可惜是 $O(N^2)$ 的。

考虑在 $k$ 很小的时候这个做法非常浪费,注意到 $dep_i$ 模 $2^{k}$ 同余的节点被差分到的是一样的,然后就做完了。

就这?就这?就这?就这?

和 ZJOID2T2 一比,高下立分啊……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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

题目链接

首先必然可以反演,然后就变成这题究极弱化版了。注意可以只选择能使图联通的边集跑行列式。

兄啊 D2T3 怎么放的是一道 sb 二合一啊

就这?就这?就这?就这?

和 ZJOID2T3 一比,高下立分啊……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#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);
}