[AT_abc431_f] [ABC431F] Almost Sorted 2 题解

条件就是在说，前一项最多比后一项大

D

。

考虑从大到小地填数。设当前填到数值

i

，

c_i

表示序列中有多少个

i

，那么这些数只能插到当前序列的头部，或者满足

x\le i+D

的

x

后方。设

s_i=s_{i-1}+c_i

即

c

的前缀和，则可以插入的空数量为

T=s_{i+D}-s_i+1

。

下面分析插入的方案数怎么计算。第一个被插入的

i

有

T

种方案，第二个在此基础上可以选择插入到第一个后方，有

T+1

种方案，以此类推。由于每个

i

完全相同，而前面却对

i

钦定了顺序，所以最后还要除以

c_i!

。推知方案数为

\displaystyle\frac{T(T+1)\cdots(T+c_i-1)}{c_i!}=\frac{(T+c_i-1)!}{(T-1)!c_i!}=\binom{T+c_i-1}{c_i}=\binom{s_{i+D}-s_{i-1}}{c_i}

。

最终答案如下。

\boxed{\prod_{i=1}^{10^6}\binom{s_{i+D}-s_{i-1}}{c_i}}

计算组合数，设

p=998244353

，可以先求出

\text{frac}_i=(i\times\text{frac}_{i-1})\bmod p

表示

i

的阶乘，然后费马小定理求出

\text{inv}_{10^6}=(\text{frac}_{10^6})^{p-2}\bmod p=(\text{frac}_{10^6})^{-1}\bmod p

。然后递推

\text{inv}_{i-1}=(i\times\text{inv}_i)\bmod p

，于是

\displaystyle\binom{n}{m}=(\text{frac}_n\times\text{inv}_m\times\text{inv}_{n-m})\bmod p

。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=1000007,p=998244353;
ll n,D,c[maxn],s[maxn],ans,frac[maxn],inv[maxn];
ll qpow(ll a,ll b){ll E=1; for(;b;b>>=1,a=a*a%p)if(b&1) E=E*a%p; return E;}
void init(void){
	frac[0]=1;
	for(ll i=1;i<maxn;i++) frac[i]=frac[i-1]*i%p;
	inv[maxn-1]=qpow(frac[maxn-1],p-2);
	for(ll i=maxn-1;i>=1;i--) inv[i-1]=inv[i]*i%p;
}
ll C(ll a,ll b){return (a<b||b<0)?0:frac[a]*inv[b]%p*inv[a-b]%p;}
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>D,init();
	for(ll i=1,x;i<=n;i++) cin>>x,c[x]++;
	for(ll i=1;i<maxn;i++) s[i]=s[i-1]+c[i];
	ans=1;
	for(ll i=maxn-1;i>=1;i--)if(c[i]) ans=ans*C(s[min(maxn-1,i+D)]-s[i-1],c[i])%p;
	cout<<ans<<"\n";
	return 0;
}

[AT_abc431_f] [ABC431F] Almost Sorted 2 题解

文章操作

相关推荐

评论

[AT_abc431_f] [ABC431F] Almost Sorted 2 题解