这波史无前例abc做出六个题，G没有突破成功...是一个容斥...也可以是一个组合数学，我用组合数学做的，上大分！
而且dirt率超级低：
比赛链接：ABC266
A.Middle Letter
输出奇数长度的中间字符串的字母
cout<<s[s.size()/2];即可
B.Modulo Number
给你一个$-10^{18}\leq x\leq 10^{18}$的数字，请对$998244353$取模，输出正数。
这个题考点就是负数，比如-5 % 2的结果是-1而不是1，所以我们先取模然后再加上mod再取模，这样就能解决负数问题，正数也没有影响。
inline void Case_Test()
{
cin>>n;
cout<<((n%mod)+mod)%mod;
}C.Convex Quadrilateral（判断凸多边形）
顺时针给你一个四边形的四个点的坐标，判断是否是凸多边形。
方法一：用计算几何的方法，叉积判断是正还是负，请见POJ2318 Toys（计算几何）- CarryNotKarry。
每次把相邻的两个点及其本身进行判断，判断下一个点是否在上一条线的一边，具体自己确定。
代码：
PII p[6];
int cross(PII a,PII b,PII c)
{
PII r1(c.fi-b.fi,c.se-b.se),r2(a.fi-b.fi,a.se-b.se);
int res = r1.fi*r2.se-r1.se*r2.fi;
return res;
}
inline void Case_Test()
{
for (int i=1;i<=4;i++)
cin>>p[i].fi>>p[i].se;
p[5] = p[1];
p[0] = p[4];
bool ok = true;
for (int i=1;i<=4;i++)
{
if (cross(p[i-1],p[i],p[i+1])<0)
ok = false;
}
if (ok) Yes;
else No;
}方法二：用面积计算，如果是凸多边形，将四边形切成两个三角形面积相加是相等的。
而如果不是，那么面积相加是不相等的。
上面两三角形面积相加相等，下面两三角形面积相加不相等
代码：
def solve():
xa, ya = MI()
xb, yb = MI()
xc, yc = MI()
xd, yd = MI()
def S(x1, y1, x2, y2, x3, y3):
a = ((x1 - x2) ** 2 + (y1 - y2) ** 2) **.5
b = ((x2 - x3) ** 2 + (y2 - y3) ** 2) **.5
c = ((x3 - x1) ** 2 + (y3 - y1) ** 2) **.5
p = (a + b + c) / 2
return (p * (p - a) * (p - b) * (p - c)) **.5
eps = 1e-8
if abs(S(xa, ya, xb, yb, xc, yc) + S(xc, yc, xd, yd, xa, ya) - S(xb, yb, xc, yc, xd, yd) - S(xd, yd, xa, ya, xb, yb)) < eps:
print('Yes')
else:
print('No')
D.Snuke Panic (1D)（DP）
题意：你现在在一维的线段上，有5个坐标分别是$0,1,2,3,4$，你现在在$0$位置上，你每秒可以向左向右走一步，然后你有若干次奖励，奖励在$T_i$时刻出现在$X_i$，奖励增加$A_i$，你最大可以获得的收益是多少。
思路：一开始还不会写，突然想到DP可以这么定义dp[i][j=0/1/2/3/4]表示第i时刻在第j处的最大奖励。
那么转移方程如何来？对于当前的dp[i][j]只能从上一个时间i-1的相邻转移j-1/j+1而来，如果是边界那么只有一种能转移。二者取max即可，如果当前有奖励那么当然加上。
代码：
int dp[N][5];
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>t[i]>>x[i]>>a[i];
for (int i=0;i<5;i++)
dp[0][i] = -INF;//一开始都设置为-INF
dp[0][0] = 0;//只有初始位置才是0可以开始转移
int cur = 1;
for (int i=1;i<=100000;i++)
{
for (int j=0;j<4;j++)
dp[i][j] = max({dp[i-1][j-1],dp[i-1][j+1],dp[i-1][j]});
dp[i][0] = Max(dp[i-1][0],dp[i-1][1]);
dp[i][4] = Max(dp[i-1][4],dp[i-1][3]);
if (t[cur]==i)//如果当前时间有奖励
{
dp[i][x[cur]] += a[cur];//那么这个时候就加上
cur++;//判断的奖励往下移动一个
}
for (int j=0;j<=4;j++)
ans = Max(ans, dp[i][j]);//途中都判断一下
}
cout<<ans;
}E.Throwing the Die（期望DP）
题意：你有一个六面骰子，你将进行$n$次试验：
- 如果现在是第$n$轮，你骰到了$x$，那么积分是$x$
- 如果在途中可以选择结束，骰到了$x$那么积分就是$x$不再继续。
问$n$轮过后的期望是多少。
思路：
当$n=1$的时候，答案是$3.500000$，不难想，选到什么就是什么。
那么多的时候呢？答案就变了，假如当前是$5$，我骰到$2$肯定是不好的，所以我选择到$5$就结束。
我们当然希望选到$6$就直接结束。
定义$f[i]$为第$i$轮的期望，那么$f[1]=3.500000$，然后开始枚举$n$次递推：
并且枚举骰出的$j=1,2,3,4,5,6$
- 如果当前$j<f[i-1]$这么说明我当前这一次比上次期望还低，那么就有$\frac{1}{6}$的概率选到这个，代表没有贡献，不如不骰这次。
f[i]+=f[i-1]/6.0 - 否则，那么我肯定选择骰这一次，并且概率直接替换这次的。
f[i]+=j/6.0
代码：
double f[110];
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=6;i++)
f[1] += 1.0/6.0*(double)i;
for (int i=2;i<=n;i++)
{
for (int j=1;j<=6;j++)
if (j<f[i-1])
f[i] += f[i-1]/6.0;
else
f[i] += j/6.0;
}
cout<<fixed<<setprecision(10)<<f[n];
}F.Well-defined Path Queries on a Namori（基环树）
题意：给你一个$n$点$n$边的图，有若干次询问，问点u到点v是否是一条简单路径（也就是是否只有一条路到达）
思路：这个题就是基环树，可以见AcWing1738.蹄球（基环树｜思维） - CarryNotKarry。
n点n边的基环树，也就是中间是个换，环上都一个子树（包括自己）
我们不难想到，只要经过这个环，那么就是一定不是简单路径，环上的两个点也是一样的。
那么我们可以用到基环树最基本的一个操作，对环上的点对其子树染色：
对子树染色
其实很简单，从点开始并且只需要判断不要染到环上的即可。
那么如何判断环？直接拓扑排序即可。
最后可以把问题转化为是否是同样一个颜色即可。
代码：
inline void dfs(int x)
{
col[x] = col_num;
for (int i=head[x];i;i=edge[i].next)
{
int y = edge[i].to;
if (vis[y]||col[y]) continue;
dfs(y);
}
}
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
{
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
in[u]++;in[v]++;
}
queue<int> q;
for (int i=1;i<=n;i++)
{
vis[i] = 1;
if (in[i]==1) q.push(i);
}
while (!q.empty())
{
int x = q.front();q.pop();
vis[x] = false;
for (int i=head[x];i;i=edge[i].next)
{
int y = edge[i].to;
if (vis[y]==false) continue;
in[y]--;
if (in[y]==1) q.push(y);
}
}
for (int i=1;i<=n;i++)
{
if (!vis[i]) continue;
++col_num;
dfs(i);
}
cin>>p;
while (p--)
{
cin>>x>>y;
if (col[x]==col[y]) Yes;
else No;
}
}G.Yet Another RGB Sequence（组合数学）
题意：你有$r$个R，$g$个G，$b$个B，你需要对其进行排列，并且有且仅有$k$个RG。例如r=2,g=2,b=1,k=1中符合条件的有RGRBG，但是RGRGB就不可以，因为RG出现了两次
思路：我一开始想那肯定先从中选出$k$个R和G，这样变成了有$r-k$个R，$g-k$个G，$b$个B，$k$个RG。那么就是：
这样就是固定RG，其他任意排列，但是其他任意排列也会导致会产生新的RG，所以需要用到容斥——官方题解
但是可以换种方法思考：
我们先不管G，先管$r-k$个R，$b$个B，$k$个RG（先不管$g-k$个G）。这样排列则有：
$$
R^{r-k}B^bRG^k=\frac{(r-k+b+k)!}{(r-k)!\cdot b!\cdot k!}
$$
那么这里面一共有$r-k+b+k=r+b$个元素，其中有$r-k$个R，我要放剩下的G则不能放在R后面，所以现在问题变成了
给你$r+b-(r-k)=b+k$个
o，你需要插入$g-k$个*，问有多少种方案。
_o_o_o_o_o_其中要插入若干的*，_是空隙，且一个空隙能插入多个*。比如ooo**oo***oo
再简单化一下：你有$a$个o，需要插入$b$个*有多少种方案。
其实就是$a+b$个位置，选出$b$个给MARKDOWN_HASH3389dae361af79b04c9c8e7057f60cc6MARKDOWNHASH，所以答案是$\binom{a+b}{b} $，也就是$C{a+b}^b$。
所以上面插入$g-k$个MARKDOWN_HASHdfcf28d0734569a6a693bc8194de62bfMARKDOWNHASH答案就是$\binom{b+k+g-k}{g-k}=C{g-k}^{b+g}$
那么答案就是二者相乘
$$
ans = \frac{(r-k+b+k)!}{(r-k)!\cdot b!\cdot k!} \times C_{g-k}^{b+g}
$$
代码：
int ksm(int a,int b,int p=mod,int res=1)
{
for( ; b ; a=a*a%p, b>>=1) if(b&1) res=res*a%p;
return res;
}
int fac[N],inv[N];
void init(int n=N-2)
{
inv[0]=fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void Case_Test()
{
cin>>r>>g>>b>>k;
ans = fac[r+b]*inv[r-k]%mod*inv[b]%mod*inv[k]%mod*C(b+g,g-k)%mod;
cout<<ans;
}