题解 P7501

dead_X · 2021-04-07 09:33:54 · 题解

思路

下文记 R_i=2r_i-1。

• \text{type}=0

显然如果答案存在，我们放完所有兵营后必定还剩下 m-\sum R_i 个空位置。

因此，我们只需要在 m-\sum R_i+n 个位置中，有序地选出 n 个，依次将这些位置钦定为第 i 个兵营，剩余位置定为空地，即可算出所有方法数。

• \text{type}=1

考虑钦定两侧兵营的 r_i。

若最左侧为第 p 个兵营，最右侧为第 q 个兵营，将 m 向左延长 R_p-r_p 格子，向右延长 R_q-r_q 个格子，同时让所有兵营的摆放条件仍然按照 \text{type}=0 时的条件计数，方法仍然可以形成一一对应，只需要将延长出来的格子去掉即可。

因此，我们可以做到 O(n^2+m)，但是过不去。

注意到 r_i 的值域只有 10^3，我们可以转而枚举 r_i，这样的复杂度为 O(r_i^2+m)，即可通过。

代码

//愿神 zhoukangyang 指引我。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int a[1000003],b[1000003];
const int p=998244353;
int n=read(),m=read(),op=read();
int qp(int x,int y)
{
    int res=1;
    for(int t=x; y; y>>=1,t=t*t%p) if(y&1) res=res*t%p;
    return res;
}
int fac[1000003],ifac[1000003];
int A(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*ifac[n-m]%p;
}
int C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*ifac[n-m]%p*ifac[m]%p;
}
void solve0()
{
    int s=0;
    for(int i=1; i<=n; ++i) s+=a[i];
    if(s>m)
    {
        puts("0");
        return ;
    }
    int A=(m-s)+n,ans=1;
    for(int i=A; i>A-n; --i) ans=ans*i%p;
    printf("%lld\n",ans);
    return ;
}
int G[2003],S[1003];
void solve1()
{
    if(n==1)
    {
        printf("%lld\n",m);
        return ;
    }
    int s=0;
    fac[0]=ifac[0]=1;
    for(int i=1; i<=m; ++i) fac[i]=fac[i-1]*i%p,ifac[i]=qp(fac[i],p-2);
    for(int i=1; i<=n; ++i) s+=a[i];
    int ans=0;
    for(int i=1; i<=n; ++i) 
    {
        for(int j=0; j<=1000; ++j) G[b[i]+j]=(G[b[i]+j]+S[j])%p;
        ++S[b[i]];
    }
    for(int i=0; i<=2000; ++i) if(G[i]) ans=(ans+G[i]*A(m+i-s+n,n)%p)%p;
    printf("%lld\n",ans*qp(C(n,n-2),p-2)%p);
    return ;
}
signed main()
{
    for(int i=1; i<=n; i++) b[i]=read(),a[i]=(b[i]<<1)-1,--b[i];
    if(op) solve1();
    else solve0();
    return 0;
}