锦标赛游戏 题解【竞赛图】【递推】【排列组合】【构造】

点击量：201

    解决竞赛图问题是需要一些技巧的。

目录

问题描述

\(\text{YJC}\)很喜欢玩游戏，今天他决定和朋友们玩锦标赛游戏。

锦标赛游戏的规则是这样的：一共有\(i(1\le i\le n)\)个人参与游戏，每个人都编上号（ 之后用编号代替人）。任意两个人之间都要进行一场比赛（ 即单循环赛制），每一场比赛双方获胜的概率都是\(0.5\)。对于两个人\(x\)和\(y(1\le x,y\le i)\)，如果\(x=y\)或存在一个序列\((a_1,a_2,\dots ,a_m)(m\ge 2)\)，满足\(a_1\)战胜了\(a_2\)，\(a_2\)战胜了\(a_3\)，…，\(a_{m-1}\)战胜了\(a_m\)，且 \(a_1=x\)，\(a_m=y\)，则称\(x\)不弱于\(y\)。如果\(x\)不弱于\(y\)且\(y\)不弱于\(x\)，则称\(x\)和\(y\)是实力相当的。比赛结束后会给每个人发奖金。如果某个人 j(1≤j≤i)有 k(1≤k≤n)个人和他实力相当，则给他发 dk 元奖金。 奖金最多的人获胜。

\(\text{YJC}\)很想赢得游戏，但他太笨了，他想让你帮他算出对于每一个\(i\)，所有编号的期望奖金的最大值是多少。这个数字可能不是有限小数，所以你需要求的是答案\(\bmod 998244353\)的结果。

输入格式

第一行包含一个整数\(n\)，表示最大人数。

接下来\(n\)行，第\((i+1)\)行包含一个整数\(d_i\)，表示有\(i\)个人实力相当时获得的奖金。

输出格式

输出\(n\)行，第\(i\)行包含一个整数，表示\(i\)个人参与游戏时所有编号的期望奖金的最大值\(\bmod 998244353\)的结果。

输入输出样例

输入样例：

3
1
2
3

输出样例：

1
1
499122178

说明

对于\(30\%\)的数据，满足\(n\le 7\)。

对于\(100\%\)的数据，满足\(n\le 3000\)。

题解：

    第一次接触竞赛图有关的问题，思考方式和正常图论题都不一样。

    首先要把这个题的问题转变为图来表示。\(x\)不弱于\(y\)表示存在一条边\(x\rightarrow y\)，或\(x=y\)，如果\(x\)不弱于\(y\)且\(y\)不弱于\(x\)，说明\(x=y\)或\(x\)与\(y\)在同一个强连通分量上。这个题的模型是锦标赛模型，也就是我们常说的竞赛图。竞赛图就是图中任意两点都有一条有向边相连，这条有向边的方向不是一定的。

    竞赛图表示了一场单循环赛制比赛的结果，正如题目所说的那样，如果\(x\)打败了\(y\)，则把\(x\)向\(y\)连一条边。

    于是我们需要找的是所有强连通分量，在同一个强连通分量中，与每个点实力相当的点数是一致的，也就是说在一个大小为\(k\)的强连通分量中，每个点都与\(k\)个点实力相当。

    但是一个有\(n\)个点的竞赛图的连边方案是\(2^{\frac{n(n-1)}2}\)，如果全部枚举是\(2^{21}\)，可以拿到\(30\%\)的部分分。而\(n=3000\)级别的数据就无法枚举了，但是因为没有给出一个固定的图，所以这样的题要考虑计数问题。

    因为这是一个有向图，所以可以被缩成一个DAG。缩点后的每一个点都是一个强连通分量。我们可以枚举拓扑排序的最后一个强连通分量的大小，此时图被分成了两个部分，假设最后一个强连通分量的大小枚举为\(i\)：

    我们知道最后一部分强连通分量作为了拓扑排序的最后一个点，因此图中左边到右边只有向右的边，而竞赛图必须保证每两个点之间直接相连，因此方案唯一，不需要额外统计，同时也保证了两侧分别是竞赛子图。现在我们需要知道大小为\(i\)的强连通竞赛图有多少种，而左边一部分是不用刻意构造它的形态的，也不一定是强连通的（其实是为了下一步的推导做准备）。设大小为\(i\)的无编号强连通的竞赛图数量为\(a_i\)，则上述情况的状态数就有：

\[C_n^i\cdot a_i\cdot 2^{\frac{(n-i)(n-i-1)}2}\]

    其中\(C_n^i\)表示右侧\(i\)个点的编号选取的方案数；\(a_i\)表示大小为\(i\)的强连通图数量；\(2^{\frac{(n-i)(n-i-1)}2}\)表示左侧竞赛子图方案数，主要由边的方向来决定。

    如果我们枚举\(i\)，就会得到所有大小为\(n\)的强连通竞赛图方案，也就是原图可能出现的所有情况。原图可能出现的所有情况用边的方向来表示依然是\(2^{\frac{n(n-1)}2}\)种。那么我们枚举\(i\)的过程中列出一个等式：

\[2^{\frac{n(n-1)}2}=\sum_{i=1}^n C_n^i \cdot a_i \cdot 2^{\frac{(n-i)(n-i-1)}2}\]

    根据数列的知识，我们可以从中提取（构造）出\(a_n\)，当右侧\(i=n\)时，有\(C_n^n\cdot a_n\cdot 2^{\frac{(n-i)(n-i-1)}2}=a_n\)，也就是说，等式右边就是

\[\sum_{i=1}^{n-1}C_n^i \cdot a_i \cdot 2^{\frac{(n-i)(n-i-1)}2}+a_n\]

    移项可以得到

\[a_n=2^{\frac{n(n-1)}2}-\sum_{i=1}^{n-1}C_n^i \cdot 2^{\frac{(n-i)(n-i-1)}2},a_1=1\]

    我们现在递推得到了大小为\(i\)的强连通竞赛图方案数。接下来我们还要进行递推。

    题目要求的是所有人的期望奖金最大值，可以知道每个人都可能在任意方案的任意位置，因此可以把这个最大值去掉，即我们求的是所有人的期望奖金。因此我们可以先求出所有竞赛图中每个人的奖金和，然后除以人数再除以竞赛图的方案数。

    设\(f_i\)表示大小为\(i\)的强连通竞赛图的所有方案中每个人的奖金总和。依然枚举拓扑排序的最后一个点大小，同样借助上面那个图，因为保证右侧是强连通的，所以右侧每个点与之“实力相当”的点的个数都是\(i\)。左侧由于是任意的竞赛子图，所以左侧所有种类图的奖金和就是\(f_{n-k}\)，右侧的划分方案数是\(C_n^i\cdot a_i\)，每个方案对这\(i\)个点分别有\(d_i\)的奖金，同时要被计算的次数是左边图的种类数，因此可以列式：

\[f_n=\sum_{i=1}^n C_n^i \cdot a_i(f_{n-i}+2^{\frac{(n-i)(n-i-1)}2}\cdot d_i\cdot i)\]

    最后在第\(i\)行输出\(\frac{f_i}{i\cdot 2^{\frac{i(i-1)}2}}\)就可以了。时间复杂度为\(O(n^2)\)。

Code：

#include<cstdio>
#include<cstring>
long long two[5000000];//预处理出2的幂
long long inv(long long x)//现场计算逆元
{
    int y=998244351;
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans=ans*m%998244353;
        m=m*m%998244353;
        y>>=1;
    }
    return ans;
}
int d[3010];
long long f[3010],a[3010];
long long tri[3010][3010];//预处理组合数
int main()
{
    two[0]=1;
    for(int i=1;i<=5000000;++i)
        two[i]=two[i-1]*2%998244353;
    int n;
    scanf("%d",&n);
    tri[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        tri[i][0]=1;
        for(int j=1;j<=i;++j)
            tri[i][j]=(tri[i-1][j-1]+tri[i-1][j])%998244353;
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&d[i]);
    for(int i=1;i<=n;++i)
    {
        a[i]=two[i*(i-1)/2];
        for(int j=1;j<i;++j)//递推a[i]
            a[i]=(a[i]-tri[i][j]*a[j]%998244353*two[(i-j)*(i-j-1)/2])%998244353;
        a[i]=(a[i]+998244353)%998244353;
    }
    for(int i=1;i<=n;++i)//递推f[i]
        for(int j=1;j<=i;++j)
            f[i]=(f[i]+tri[i][j]*a[j]%998244353*(f[i-j]+two[(i-j)*(i-j-1)/2]*j%998244353*d[j]%998244353))%998244353;
    for(int i=1;i<=n;++i)
        printf("%lld\n",f[i]*inv(two[i*(i-1)/2])%998244353*inv(i)%998244353);
    return 0;
}