R1
F. 开关灯
初始有编号 \(1\sim n\) 的 \(n\) 盏关闭的灯，第 \(i\) 盏灯权值为 \(a_i\)，随机选取 \(1\sim n\) 的一个排列依次开灯；每次开灯后设当前亮灯极大连续段数量为 \(c\)，本次打开第 \(i\) 盏灯则获得 \(a_i\cdot c\) 的分数，求总得分的数学期望，答案对 \(998244353\) 取模；多组测试数据，数据范围：\(1\le T\le 2\times 10^5\)，\(1\le n\le 2\times 10^5\)，\(0\le a_i<998244353\)，所有测试数据的 \(n\) 总和不超过 \(2\times 10^6\)。
分块计算每个位置 \(i\) 被点亮时对答案的贡献。
考虑连通块的一个常见转化：\(c=c_1-c_{11}\)，\(c_{1},c_{11}\) 分别表示 1 和 11 的个数。比如 11101 就有 \(4\) 个 1，\(2\) 个 11。
显然 \(c_1\) 的值为 \({1,2,\cdots,n}\) 中等概率选取一个，于是 \(E(c_1)=\dfrac{\sum_{i=1}^n i}{n}=\dfrac{n+1}{2}\)。
如何求出 \(c_{11}\) 的期望？首先有两种情况：
- Case 1：点燃 \(i\) 之后，和旁边的构成了一个
11（新增的11包含 \(i\)），要求在点亮 \(i\) 前他的邻居已被点亮，故概率为 \(1/2\) - Case 2:点燃 \(i\) 之前就有的
11（新增的11不含 \(i\)）。假设三盏灯为 \((x,y,i)\)，\(i\) 为当前灯，那么全排列一共有 \(3!=6\) 种，而 \(x,y\) 在 \(i\) 前的情况有 \((x,y,i),(y,x,i)\) 两种，故概率为 \(1/3\)
需要分在 \(i\) 边界和在中间两种情况。
- Case 1: 在边界，只有一种情况：\((1,2)\)（左边界）、\((n-1,n)\) 右边界，所以贡献为 \(1 \times \dfrac12=\dfrac12\)；在中间，显然有 \((i-1,i),(i,i+1)\) 两种情况，贡献为 \(2 \times \dfrac12=1\).
- Case 2: 在边界，只有 \(n-2\) 种情况（\(i1111111\)，除了开头的这个 \(i\) 剩下的 \(n-1\) 个
1组成 \(n-2\) 对，右边界也同理。也可以用 \(n-1\) 减去 Case 1 的一种理解），贡献为 \(\dfrac{n-2}3\)；在中间，有 \(n-3\) 种（\(n-1\) 减去 Case 1 的两种），贡献为 \(\dfrac{n-3}{3}\)。
最终依据期望的线性性质，推出：当点燃 \(i\) 时，连通块数 \(c\) 的期望：
答案为
注意当 \(n=1\) 时，期望得分就是 \(a_1\)，要特判。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=2e5+7;
constexpr int mod=998244353;
int n;
ll a[N];
inline ll ksm(ll a,ll b)
{ll s=1;while(b){if(b&1) s=s*a%mod;a=a*a%mod;b>>=1;}return s;
}
inline ll solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];if(n==1) return a[1];ll ans=(a[1]+a[n])%mod*(n+4)%mod;ll tmp=0;for(int i=2;i<n;i++) (tmp+=a[i])%=mod;(ans+=tmp*(n+3))%=mod;ans=ans*ksm(6,mod-2)%mod;return ans%mod;
}
int main()
{
// freopen("neuvillette.in","r",stdin);
// freopen("neuvillette.out","w",stdout);cin.tie(0)->sync_with_stdio(0);int T;cin>>T;while(T--) cout<<solve()<<'\n';cout.flush();return 0;
}
R3
I. Six Grade
共有 \(n\) 道题目与 \(n\) 个选项构成一一对应的正确答案排列，第 \(i\) 道题的标准答案仅为 \(a_i,b_i\) 二者之一，你需要给出一个答题排列（每题选一个限定范围内的选项，整体构成排列），最大化答对题数的数学期望，输出该最大期望值并对 \(998244353\) 取模；多组数据，数据范围：\(1\le T\le10，3\le n\le 10^6\)。
发现只有两个可能的选项，所以考虑建图，每一条边对应一个题，边的两个顶点为选项。然后我们惊人地发现建出来的图是一个基环树，然后问题就变成了给每条边定向，要求每个节点的入度都为 \(1\) 的问题了。每条边所指的点代表这道题的答案。
发现如果是方向是内向（从环外向环内），那么就直接爆炸了，因为可能出现一个题根本不选或者是两个题的答案都为同一个的现象。所以必须是外向。
此时树上的结点的情况就只有一种了，所以贡献为 \(1\)，环上由于不知道是顺时针还是逆时针，所以只能生死二选一了，贡献为 \(1/2\)。
我不知道为什么题解写 \(2\) 的逆元是 \(\dfrac{mod+1}{2}\) 啊。我只会 \(2^{mod-2}\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e6+7;
constexpr int mod=998244353;
int n;
int dep[N];
vector<int> g[N];
void dfs(int u,int fa,int &len,int &cnt) //len环长，cnt连通块大小
{bool flag=0; //特判二元环，跳过第一个回到父亲节点的，如果是第二次，就不跳 cnt++;for(int v:g[u]){if(v==fa&&flag==0){flag=1;continue;}if(dep[v]!=-1) //找到环{len=dep[v]-dep[u]+1;continue;}dep[v]=dep[u]+1;dfs(v,u,len,cnt);}
}
inline ll ksm(ll a,ll b)
{ll s=1;while(b){if(b&1) s=s*a%mod;a=a*a%mod;b>>=1;}return s;
}
inline ll solve()
{cin>>n;for(int i=1;i<=n;i++) g[i].clear();for(int i=1,u,v;i<=n;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(int i=1;i<=n;i++) dep[i]=-1;ll ans=0;for(int i=1;i<=n;i++){if(dep[i]==-1){dep[i]=1;int len=0,cnt=0;dfs(i,0,len,cnt);
// cerr<<len<<' '<<cnt<<'\n';(ans+=len*ksm(2,mod-2)%mod+(cnt-len))%=mod;}}return ans;
}
int main()
{
// freopen("neuvillette.in","r",stdin);
// freopen("neuvillette.out","w",stdout);cin.tie(0)->sync_with_stdio(0);int T;cin>>T;while(T--) cout<<solve()<<'\n';cout.flush();return 0;
}
/*
基环树，环上的贡献1/2，不在环上贡献1（一定可以确定一个答案）
这是一个基环树森林，需要并查集划分连通块
*/