模拟赛
T1
简单做法：
发现本题所有运算全是加法
直接记录c,s之和
转移即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
const int MOD=998244353;
int dp[1005][1005][2];
int a[1005][1005],c[1005][1005][2],sum[1005][1005][2];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int n=read(),m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char s;cin>>s;if(s=='.') a[i][j]=1;}}sum[1][1][0]=sum[1][1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i-1][j]){jiaa(sum[i][j][0],(sum[i-1][j][0]+sum[i-1][j][1])%MOD);jiaa(c[i][j][0],(c[i-1][j][0]+sum[i-1][j][0]*(i*j)%MOD+sum[i-1][j][1]*(i*j)%MOD)%MOD);jiaa(dp[i][j][0],(dp[i-1][j][0]+c[i-1][j][0]+sum[i-1][j][0]*(i*j)%MOD+dp[i-1][j][1]+sum[i-1][j][1]*(i*j)%MOD)%MOD);}if(a[i][j-1]){jiaa(sum[i][j][1],(sum[i][j-1][0]+sum[i][j-1][1])%MOD);jiaa(c[i][j][1],(c[i][j-1][1]+sum[i][j-1][1]*(i*j)%MOD+sum[i][j-1][0]*(i*j)%MOD)%MOD);jiaa(dp[i][j][1],(dp[i][j-1][1]+c[i][j-1][1]+sum[i][j-1][1]*(i*j)%MOD+dp[i][j-1][0]+sum[i][j-1][0]*(i*j)%MOD)%MOD);}}}if(!a[n][m]){cout<<0<<'\n';return 0;}int ans=(dp[n][m][0]+dp[n][m][1])%MOD;ans=ans*ksm(2,MOD-2,MOD)%MOD;cout<<ans<<'\n';return 0;
}
高级做法：
按拐点dp
前缀和优化
实现较为麻烦
T2
可以建出虚树
直接跑dfs求树的重心即可
或者观察：
点集的重心⼀定是“dfs序中位数”的祖先
此处，若点集⼤⼩为奇数，“dfs序中位数”即为点集按 dfs 序排序后，最中间的点
若为偶数，排序后最中间的点有两个，重⼼⼀定是它们之⼀的祖先
通过倍增的⽅法找到重⼼
具体地，可以发现重心⼀定是“中位数”的所有祖先（包括“中位数”本⾝）中，满⾜“条件1”的、深度最深的⼀个
若点集大小为偶数，对中间两个点分别找一次重心
取dep较大的即可
带权做法类似
T3
将偶数的边连两次，奇数的边连一次
找欧拉路径即可
T4
数学！
容斥原理
图论
最小生成树
kruskal prim
brouvka:每次取每个点的最小出边，合并，直到只剩一个点
最短路
https://www.luogu.com.cn/problem/P4568
分层图
https://www.luogu.com.cn/problem/UVA1151
暴力用哪个套餐
每次套餐内的点合并，跑prim
复杂度O(n2*2q)小常数2e8能过
https://www.luogu.com.cn/problem/P1396
求最小瓶颈路
易证一定是最小生成树上的路径
若多测树上倍增即可
https://www.luogu.com.cn/problem/P3008
是不是可以SPFA
对所有的双向边联通块缩点
一定是dag
拓扑排序更新dis
欧拉路径
欧拉路径存在，当且仅当图是联通图，且度数为奇数的点的个数不超过 2
-
如果度数为奇数的点个数为 0，则欧拉路⼀定是欧拉回路：即起点和终点相同
-
如果度数为奇数的点个数为 2，则欧拉路径必定从它们中的⼀个出发，并在另⼀个终⽌
构造方案将起点终点连边，求欧拉回路即可
若没有欧拉回路，如何构建？
容易发现奇度数的点一定是偶数个
将这些奇度数的点两两连边即可
二分图
二分染色当且仅当不存在奇环
联通分量
并查集维护到fa的路径奇偶性
若su^sv==w%2就存在答案
注意若联通块内存在奇环，一定有答案
CF547D
对每个点，横纵坐标连边
形成的图强制补成有欧拉回路的图
跑欧拉回路即可
（欧拉回路定向题，从x->y染红，反之染蓝）
T3 加强版
对于所有奇度数的点连边
边权是原图的最短路
对新图进行最小匹配