题解：P14639 【OIMO Round 1】世界线

Freezyfish · 2026-08-07 21:06:48 · 题解

很好的组合数学让我的大脑旋转。

出题人建议评黄？

思路

发现一个重要性质：把序列排序成为序列 C，你考虑合法序列倒着看一定是 C 从两边到中间的扩展，原因倒着看是如果一个数既有大于他的没取，又有小于他的没取，那么到最后他一定不是前缀最小值或最大值，前缀大于，小于他的数都出现了。

如果是一个排列，那么就很简单：答案是 2^n，考虑每次取 C 要么选前缀，要么选后缀的。

序列怎么做？你发现如果选得只剩一种数了，那么她就只有一种选法了，你就枚举最后这个数是谁即可。你钦定最后第一次到达只有一种数的状态时，这个数还有多少个，那么上一个选的数就不能是这个数。

排列组合计算。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
} 
const int N=1e6+15,mod=998244353;
int p[N];
int n;
int qp[N];
int ans=0;

int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=(res*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return res;
}

inline int C(int a,int b)
{
    if(a<b)return 0;
    return qp[a]*qmi(qp[b],mod-2)%mod*qmi(qp[a-b],mod-2)%mod;
}
signed main() 
{
    n=read();
    qp[0]=1;
    for(int i=1;i<=n;i++)p[i]=read(),qp[i]=qp[i-1]*i%mod;
    sort(p+1,p+1+n);
    int l=1;
    for(int i=1;i<=n;)
    {
        l=i;
        while(p[l+1]==p[i])l++;
        ans=(ans+C(i-1+n-l,i-1))%mod;
        for(int j=1;j<=l-i;j++)
        {
            ans=(ans+C(j+i-1+n-l-1,j+i-1)%mod)%mod;
            //cout<<ans<<"\n";
            ans=(ans+C(i-1+n-l+j-1,n-l+j)%mod)%mod;
            //cout<<i-1+n-l+j-1<<" "<<n-l+j<<"\n";
        }
        //cout<<ans<<"\n";
        i=l+1;
    }
    printf("%lld\n",ans);
    return 0;
}