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

作者: wjyyy 分类: 图论,构造,竞赛图,组合数学,解题报告,递推 发布时间: 2018-10-30 15:49

点击量:33

 

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

 

问题描述

\(\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;
}

说点什么

avatar
  Subscribe  
提醒
/* */