P14639 【OIMO Round 1】世界线 TJ
0.前言
我是蒟蒻，我容斥学太差了，然后自己搞了一个比较好想的思路，如有错误欢迎各位dalao指出QwQ。
一些规定：
- \(cnt_i\)表示i这个数出现了几次。
1.分析
我们发现这个序列他是一升一降的，所以先排序找性质。
e.g
1 2 3 4 5
直接看看不太出来，考虑固定选择的第一个数。
假设固定2作为我们选择的第一个数。因为我们每次需要选的数作为最小和最大出现，所以一定是一个往两边选数的过程，而且不能跳过中间的值。比如说我选了2然后先选择5再回来选3，这样是非法的，因为这样 \(2 ＜ 3 ＜ 5\) 3就既不是最大值也不是最小值了。
先考虑没有重复值的情况。我们选择当前固定中点 \(i\) ，此时左边和右边的数选择的内部顺序是固定的，所以我们不用考虑顺序，答案就是在剩下 \((n-1)\) 个选择次数中，选择 \((i-1)\) 次去选左边的数作为最小值。即：
\[C^{i-1}_{n-1}
\]
现在考虑加上重复值。我们的计算就会失效，有很多重复的地方。
然后我们通过惊人注意力又可以发现一个美妙的性质：我最后选出来的除开固定的端点的序列，其前缀一定是 \(0\) ~ \((cnt_i-1)\) 个当前值，然后接上一个次大/小值。所以我们只需要枚举这个前缀，然后用组合数计算一下这个前缀对应的可能情况数，最后累加起来就是答案了。
2.实现
注意最后组合数的时候要仔细想一下哪些划分进左边，哪些划分进右边，不然会算漏或者算重一些情况。
有些特判我也不知道是不是必须加反正就是一坨屎山罢了QwQ。
AC code:
#include<bits/stdc++.h>
using namespace std;#define sht short
#define ll long long
#define ull long long
#define endl '\n'
#define xwy114514 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int llconst sht SHTINF=32767;
const int INTINF=0x7f7f7f7f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());
inline int readi(){int res=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c==EOF)return 0;if(c=='-')f=0;c=getchar();}while('0'<=c&&c<='9')res=(res<<1)+(res<<3)+(int)(c-'0'),c=getchar();return f?res:-res;}
inline ll readl(){ll res=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c==EOF)return 0ll;if(c=='-')f=0;c=getchar();}while('0'<=c&&c<='9')res=(res<<1)+(res<<3)+(int)(c-'0'),c=getchar();return f?res:-res;}
inline void FREOPEN(const string &IN,const string &OUT){freopen((IN+".in").c_str(),"r",stdin),freopen((OUT+".out").c_str(),"w",stdout);}
inline void xwymin(int &a,int b){a=(a<b)?a:b;}
inline void xwymax(int &a,int b){a=(a<b)?b:a;}
inline int getmin(int a,int b){return (a<b)?a:b;}
inline int getmax(int a,int b){return (a<b)?b:a;}const int N=1e6+10;
const int Mod=998244353;int n,cnt[N],jc[N],inv_jc[N],ans,p,pre,nxt;inline int qpow(int a,int b){int res=1ll;while(b){if(b&1)res=res*a%Mod;b>>=1,a=a*a%Mod;}return res;}
inline int Inv(int a){return qpow(a,Mod-2);}
inline int C(int a,int b){if(a>b||a<0)return 0;return (jc[b]*inv_jc[a])%Mod*inv_jc[b-a]%Mod;}inline void init(){jc[0]=1;for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i%Mod;inv_jc[n]=Inv(jc[n]);for(int i=n-1;i>=0;i--)inv_jc[i]=inv_jc[i+1]*(i+1)%Mod;
}signed main(){
// FREOPEN("","xwy");xwy114514;cin>>n;init();for(int i=1,a;i<=n;i++)cin>>a,cnt[a]++;for(int i=1;i<=n;i++)if(cnt[i]){if(!pre)pre=i;nxt=i;}for(int i=1;i<=n;i++){if(cnt[i]==0)continue;for(int j=0;j<=cnt[i]-1;j++){int r=cnt[i]-1;if(i!=nxt)ans=(ans+C(r-j+p,n-1-j-1))%Mod;if(i!=pre)ans=(ans+C(p-1,n-1-j-1))%Mod;if(i==pre&&i==nxt)ans=1;}p+=cnt[i];} cout<<ans<<endl;return 0;
}
3.完结撒花
★,°:.☆(￣▽￣)/$:.°★ 。