T1 电压机制
把题目转化为找那些边只被奇数环包含。
这样的话直接$dfs$生成一棵树，给每个点附上一个深度，根据其他的非树边都是返祖边
可以算出环内边的数量$dep[x]-dep[y]+1$，然后判断
如果在统计时使用差分的思想，可以复杂度降到$O(n)$，也可以用$set$多一个$log$都能过
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace AE86{
4 inline int read(){
5 int x=0,f=1;char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
8 }inline void write(int x,char opt='\n'){
9 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
10 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
11 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
12 }using namespace AE86;
13 const int NN=4e5+5;
14 int n,m,ans,dep[NN],val[NN],huan;
15 struct SNOW{int to,next,cir;bool vis;}e[NN]; int head[NN],rp=1;
16 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;}
17
18 inline void dfs(int x,int d){
19 dep[x]=d;
20 for(int i=head[x];i;i=e[i].next){
21 if(e[i].vis) continue;
22 e[i].vis=e[i^1].vis=1;
23 int y=e[i].to;
24 if(dep[y]){
25 int tmp=dep[x]-dep[y]+1;
26 if(tmp&1){
27 ++e[i].cir; ++e[i^1].cir;
28 --val[y]; ++huan;
29 }
30 else{
31 --e[i].cir; --e[i^1].cir;
32 ++val[y];
33 }
34 val[x]+=e[i].cir;
35 continue;
36 }
37 dfs(y,d+1);
38 e[i].cir=e[i^1].cir=val[y];
39 val[x]+=val[y];
40 }
41 }
42 namespace WSN{
43 inline short main(){
44 freopen("a.in","r",stdin);
45 freopen("a.out","w",stdout);
46 n=read(); m=read();
47 for(int i=1,u,v;i<=m;i++)
48 u=read(),v=read(),add(u,v),add(v,u);
49 dfs(1,1);
50 for(int i=2;i<=rp;i+=2) if(e[i].cir==huan) ++ans;
51 write(ans);
52 return 0;
53 }
54 }
55 signed main(){return WSN::main();}
T2 括号密码
咕咕咕
T3 排列
无限之环加强版，$24$种情况特判就行，然后有两种特殊情况树状数组维护左右区间值
主要就是考虑你现在要找的对应排列的大小关系，普通的排列以$2134$为例
我们以位置为行下标，$b_i$的值为列下标做前缀和数组，那么记录可以将位置和权值拆开的点对叫好的点对
比如$2134$里面的$(2,3)$就是好的，他把$1，4$划分成两段，类似的还有$(1,3)(2,3)(2,4)$（他们反过来也是好的）
那么我们可以直接找到位置 在$(2,3)$之间的权值小于$2$的数的个数 乘 位置在$3$右边的权值大于$3$的数的个数
inline void spj2134(){
for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(j+1,n,b[j]+1,n);
}
有两个排列是没有这种好的点对的，比如$2413,3142$，以下拿$2413$举例
这样的我们不能用前缀和，但可以考虑枚举$3$的位置，再枚举它前面的比他权值大的位置充当$4$
然后找$4$前面的比后面数大的个数，考虑用两个树状数组来统计$4$位移带来的影响即可
inline void spj2413(){
for(int i=4;i<=n;++i){
memset(L.tr,0,sizeof(L.tr));memset(R.tr,0,sizeof(R.tr));
int sum=0;
for(int j=1;j<i;j++) R.update(b[j],1);
for(int j=1;j<i;j++)
if(b[j]>b[i]) ans+=sum;
else{
sum+=R.query(b[j]-1);
sum-=L.query(n)-L.query(b[j]);
L.update(b[j],1); R.update(b[j],-1);
}
}
}
$UPD$建议写的时候念叨着写，错误率会降低很多
比如我写的时候就。。。。
我看到了（2，3）。。。我看到了（2，3）。。。我看到了（2，3）。。。我看到了（2，3）。。。
我看到了（1，3）。。。我看到了（1，3）。。。我看到了（1，3）。。。我看到了（1，3）。。。
烦死了旁边的$zxs$，但是我反正是一遍$91$分的。。。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=3005;
15 int a1,a2,a3,a4,b[NN],n,ans,sum[NN][NN];
16 namespace Tree_array{
17 struct tree{
18 int tr[NN];
19 inline int lowbit(int x){return x&(-x);}
20 inline void update(int x,int v){for(int i=x;i<NN;i+=lowbit(i))tr[i]+=v;}
21 inline int query(int x,int res=0){for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
22 }L,R;
23 }using namespace Tree_array;
24 inline int get(int l1,int r1,int l2,int r2){
25 return sum[r1][r2]-sum[l1-1][r2]-sum[r1][l2-1]+sum[l1-1][l2-1];
26 }
27 inline void spj1234(){
28 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[i]+1,b[j]-1)*get(j+1,n,b[j]+1,n);
29 }
30 inline void spj1243(){
31 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(1,i-1,1,b[i]-1);
32 }
33 inline void spj1324(){
34 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(j+1,n,b[i]+1,n);
35 }
36 inline void spj1342(){
37 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(i+1,j-1,b[i]+1,n);
38 }
39 inline void spj1423(){
40 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(j+1,n,b[j]+1,b[i]-1);
41 }
42 inline void spj1432(){
43 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(j+1,n,b[i]+1,b[j]-1);
44 }
45 inline void spj2134(){
46 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(j+1,n,b[j]+1,n);
47 }
48 inline void spj2143(){
49 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(j+1,n,b[i]+1,b[j]-1);
50 }
51 inline void spj2314(){
52 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[j]+1,b[i]-1)*get(j+1,n,b[i]+1,n);
53 }
54 inline void spj2341(){
55 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[i]+1,b[j]-1)*get(j+1,n,1,b[i]-1);
56 }
57 inline void spj2413(){
58 for(int i=4;i<=n;++i){
59 memset(L.tr,0,sizeof(L.tr));memset(R.tr,0,sizeof(R.tr));
60 int sum=0;
61 for(int j=1;j<i;j++) R.update(b[j],1);
62 for(int j=1;j<i;j++)
63 if(b[j]>b[i]) ans+=sum;
64 else{
65 sum+=R.query(b[j]-1);
66 sum-=L.query(n)-L.query(b[j]);
67 L.update(b[j],1); R.update(b[j],-1);
68 }
69 }
70 }
71 inline void spj2431(){
72 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(j+1,n,1,b[i]-1);
73 }
74 inline void spj3124(){
75 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,1,b[j]-1)*get(j+1,n,b[i]+1,n);
76 }
77 inline void spj3142(){
78 reverse(b+1,b+n+1);spj2413();
79 }
80 inline void spj3214(){
81 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(1,i-1,b[i]+1,b[j]-1);
82 }
83 inline void spj3241(){
84 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[i]+1,b[j]-1)*get(j+1,n,1,b[i]-1);
85 }
86 inline void spj3412(){
87 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,b[i]+1,n)*get(j+1,n,b[j]+1,b[i]-1);
88 }
89 inline void spj3421(){
90 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,b[i]+1,n)*get(j+1,n,1,b[j]-1);
91 }
92 inline void spj4123(){
93 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,1,b[j]-1)*get(j+1,n,b[j]+1,b[i]-1);
94 }
95 inline void spj4132(){
96 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(j+1,n,b[i]+1,b[j]-1);
97 }
98 inline void spj4213(){
99 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(i+1,j-1,1,b[i]-1);
100 }
101 inline void spj4231(){
102 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(j+1,n,1,b[i]-1);
103 }
104 inline void spj4312(){
105 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[i]+1,n)*get(j+1,n,b[j]+1,b[i]-1);
106 }
107 inline void spj4321(){
108 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[i]+1,n)*get(j+1,n,1,b[j]-1);
109 }
110 namespace WSN{
111 inline short main(){
112 freopen("c.in","r",stdin);
113 freopen("c.out","w",stdout);
114 n=read(); a1=read(); a2=read(); a3=read(); a4=read();
115 for(int i=1;i<=n;i++) b[i]=read();for(int i=1;i<=n;i++) sum[i][b[i]]=1;
116 for(int i=1;i<=n;i++){
117 for(int j=1;j<=n;j++) sum[i][j]+=sum[i][j-1];
118 for(int j=1;j<=n;j++) sum[i][j]+=sum[i-1][j];
119 }
120 if(a1==1&&a2==2&&a3==3&&a4==4) spj1234();
121 if(a1==1&&a2==2&&a3==4&&a4==3) spj1243();
122 if(a1==1&&a2==3&&a3==2&&a4==4) spj1324();
123 if(a1==1&&a2==3&&a3==4&&a4==2) spj1342();
124 if(a1==1&&a2==4&&a3==2&&a4==3) spj1423();
125 if(a1==1&&a2==4&&a3==3&&a4==2) spj1432();
126 if(a1==2&&a2==1&&a3==3&&a4==4) spj2134();
127 if(a1==2&&a2==1&&a3==4&&a4==3) spj2143();
128 if(a1==2&&a2==3&&a3==1&&a4==4) spj2314();
129 if(a1==2&&a2==3&&a3==4&&a4==1) spj2341();
130 if(a1==2&&a2==4&&a3==1&&a4==3) spj2413();
131 if(a1==2&&a2==4&&a3==3&&a4==1) spj2431();
132 if(a1==3&&a2==1&&a3==2&&a4==4) spj3124();
133 if(a1==3&&a2==1&&a3==4&&a4==2) spj3142();
134 if(a1==3&&a2==2&&a3==1&&a4==4) spj3214();
135 if(a1==3&&a2==2&&a3==4&&a4==1) spj3241();
136 if(a1==3&&a2==4&&a3==1&&a4==2) spj3412();
137 if(a1==3&&a2==4&&a3==2&&a4==1) spj3421();
138 if(a1==4&&a2==1&&a3==2&&a4==3) spj4123();
139 if(a1==4&&a2==1&&a3==3&&a4==2) spj4132();
140 if(a1==4&&a2==2&&a3==1&&a4==3) spj4213();
141 if(a1==4&&a2==2&&a3==3&&a4==1) spj4231();
142 if(a1==4&&a2==3&&a3==1&&a4==2) spj4312();
143 if(a1==4&&a2==3&&a3==2&&a4==1) spj4321();
144 write(ans);
145 return 0;
146 }
147 }
148 signed main(){return WSN::main();}
T4 B关系
咕咕咕，神仙$dp$套$dp$
$UPD 2021.9.29$盯顶着评论区的差评重压继续完成博客
比较神仙，是拍过的。。。（根本无法独立完成）
大概就是在最长公共子序列的$dp$方程式上进行$dp$
发现对于题目的限制$dp[n][n]>=n-2$，它限制了转移只能从$dp[i][i],dp[i-1][i],dp[i][i-1],dp[i-2][i],dp[i][i-2]$这几个状态来转移
不妨设$dp[i][S]$表示考虑了$a,b$数组的前$i$位，状态为$S$的方案数
那么还需要记录$a,b$序列的相等关系，共有四种，还需要记录上述状态的转移值，
然后可以直接搜索出所有状态，因为不多。然后对于每种状态进行转移的赋值，
因为数组空间问题，开的状态结构体里面记录的状态下标以及数值都是差值
1 inline void dfs(int x,int mx){
2 if(x>4){//1->a[i-1] 2->b[i-1] 3->a[i] 4->b[i]
3 // cout<<p.ab[1]<<" "<<p.ab[2]<<" "<<p.ab[3]<<" "<<p.ab[4]<<endl;
4 int c1=(p.ab[1]==p.ab[4]);//a[i-1]==b[i]
5 int c2=(p.ab[1]==p.ab[2]);//a[i-1]==b[i-1]
6 int c3=(p.ab[3]==p.ab[2]);//a[i]==b[i-1]
7 int c4=(p.ab[3]==p.ab[4]);//a[i]==b[i]
8 p.f[0][2]=p.f[2][0]=2;
9 p.f[1][0]=2-(c1||c2);
10 p.f[0][1]=2-(c3||c2);
11 p.f[0][0]=min(c2&&c4?0ll:2ll,min(min(2ll-(c1||c4),2ll-(c3||c4)),min(p.f[0][1],p.f[1][0])));
12 int tmp=max(max(p.ab[1],p.ab[2]),max(p.ab[3],p.ab[4]));
13 wy[++cnt]=R*(tmp>1?R-1:1)%mod*(tmp>2?R-2:1)%mod*(tmp>3?R-3:1)%mod*(tmp<=R);
14 st[cnt]=p; mp[p]=cnt;
15 return;
16 }
17 for(int i=1;i<=mx+1;i++) p.ab[x]=i,dfs(x+1,max(mx,i));
18 }
搜索状态
然后考虑状态数不多，可以进行矩阵优化加速递推（这我无法想到）。
这里解释一下那个$tmp$，他记录的是四种关系的相对大小中最大的那个数，
他恰恰也是这四个数的种类数，那么相应的计算方案数就可以使用字符集减去种类数得到
关于$calc$函数，就是给枚举的新状态进行状态的赋值操作，那个$100ll$纯属个人喜好，赋值比$3$大的数就可以
还是有一些地方不太懂，比如对于矩阵优化的可行性，希望路过的大佬提出高见
但是是拍过的就没什么要不要脸的了
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int MM=200,mod=998244353;
15 int n,R,cnt,wy[MM];
16 namespace Matrix{
17 struct Ma{
18 int m[MM][MM];
19 Ma(){memset(m,0,sizeof(m));}
20 inline void pre(){for(int i=1;i<=cnt;i++)m[i][i]=1;}
21 inline void print(){ for(int i=1;i<=cnt;i++){for(int j=1;j<=cnt;j++){cout<<m[i][j]<<" ";} cout<<endl;} }
22 };
23 inline Ma mul(Ma a,Ma b){
24 Ma c; for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++)
25 (c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod)%=mod; return c;
26 }
27 inline Ma qmo(Ma a,int b){
28 Ma c; c.pre();while(b){if(b&1) c=mul(c,a);b>>=1; a=mul(a,a);} return c;
29 }
30 }using namespace Matrix;
31
32 struct sta{
33 int f[3][3],ab[5];
34 inline void discrete(){
35 int has=0,mp[15]={};
36 for(int i=1;i<=4;i++){
37 if(!mp[ab[i]]) mp[ab[i]]=++has;
38 ab[i]=mp[ab[i]];
39 }
40 }
41 inline sta calc(int x,int y){//1->a[i-1] 2->b[i-1] 3->a[i] 4->b[i]
42 sta ti=(sta){{{0,0,0},{0,0,0},{0,0,0}},{0,ab[3],ab[4],x,y}};
43 ti.discrete();
44 ti.f[2][0]=min(ab[1]==y?f[2][0]:100ll,f[1][0]+1);
45 ti.f[0][2]=min(ab[2]==x?f[0][2]:100ll,f[0][1]+1);
46 ti.f[1][0]=min(ab[3]==y?f[1][0]:100ll,min(f[0][0]+1,ti.f[2][0]));
47 ti.f[0][1]=min(ab[4]==x?f[0][1]:100ll,min(f[0][0]+1,ti.f[0][2]));
48 ti.f[0][0]=min(x==y?f[0][0]:100ll,min(ti.f[0][1],ti.f[1][0]));
49 return ti;
50 }
51 bool operator<(const sta& x)const{
52 for(int i=0;i<=2;i++){
53 if(f[i][0]!=x.f[i][0]) return f[i][0]<x.f[i][0];
54 if(f[0][i]!=x.f[0][i]) return f[0][i]<x.f[0][i];
55 }
56 for(int i=1;i<=4;i++)
57 if(ab[i]!=x.ab[i]) return ab[i]<x.ab[i];
58 return 0;
59 }
60 }st[MM],p;
61 map<sta,int> mp;
62
63 inline void dfs(int x,int mx){
64 if(x>4){//1->a[i-1] 2->b[i-1] 3->a[i] 4->b[i]
65 // cout<<p.ab[1]<<" "<<p.ab[2]<<" "<<p.ab[3]<<" "<<p.ab[4]<<endl;
66 int c1=(p.ab[1]==p.ab[4]);//a[i-1]==b[i]
67 int c2=(p.ab[1]==p.ab[2]);//a[i-1]==b[i-1]
68 int c3=(p.ab[3]==p.ab[2]);//a[i]==b[i-1]
69 int c4=(p.ab[3]==p.ab[4]);//a[i]==b[i]
70 p.f[0][2]=p.f[2][0]=2;
71 p.f[1][0]=2-(c1||c2);
72 p.f[0][1]=2-(c3||c2);
73 p.f[0][0]=min(c2&&c4?0ll:2ll,min(min(2ll-(c1||c4),2ll-(c3||c4)),min(p.f[0][1],p.f[1][0])));
74 int tmp=max(max(p.ab[1],p.ab[2]),max(p.ab[3],p.ab[4]));
75 wy[++cnt]=R*(tmp>1?R-1:1)%mod*(tmp>2?R-2:1)%mod*(tmp>3?R-3:1)%mod*(tmp<=R);
76 st[cnt]=p; mp[p]=cnt;
77 return;
78 }
79 for(int i=1;i<=mx+1;i++) p.ab[x]=i,dfs(x+1,max(mx,i));
80 }
81 Ma base; int *it;
82 inline void prework(){
83 for(int t=1;t<=cnt;t++){
84 p=st[t]; int tmp=max(max(p.ab[1],p.ab[2]),max(p.ab[3],p.ab[4]));
85 for(int i=1;i<=tmp+1;i++) for(int j=1;j<=tmp+1||j<=i+1;j++){
86 sta pp=p.calc(i,j); if(pp.f[0][0]>2) continue;
87 it=&mp[pp];
88 if((*it)==0) *it=++cnt,st[cnt]=pp;
89 int res=0;
90 if(i>tmp && j>i) res=max(0ll,R-tmp)*(R-i)%mod;
91 else if(i>tmp||j>tmp) res=max(0ll,R-tmp);
92 else res=(tmp<=R);
93 (base.m[t][*it]+=res)%=mod;
94 }
95 }
96 }
97 namespace WSN{
98 inline short main(){
99 freopen("d.in","r",stdin);
100 freopen("d.out","w",stdout);
101 n=read(); R=read(); if(n==1) {printf("%lld\n",R*R%mod);return 0;}
102 dfs(1,0); prework();
103 Ma ans=qmo(base,n-2);int wsn=0;
104 for(int i=1;i<=cnt;i++) if(wy[i]){
105 for(int j=1;j<=cnt;j++) (wsn+=wy[i]*ans.m[i][j]%mod)%=mod;
106 }
107 write(wsn);
108 return 0;
109 }
110 }
111 signed main(){return WSN::main();}