题意

定义序列中的一个数为前缀最大值仅当其前面没有比他大的数，后缀最大值同理。问有多少个长度为n的排列满足前缀最大值数量恰好为a，后缀最大值数量恰好为b。
$n,a,ble10^5$

分析

首先分析一下性质，排列中的最大值，也就是n必然是一个前缀最大值和后缀最大值，且前缀最大值一定在n的前面，后缀最大值一定在n的后面。
设$s(i,j)$表示有多少个大小为$i$的排列满足前缀最大值数量恰好为$j$。枚举最小的数放哪里，不难得到

$$s(i,j)=s(i-1,j-1)+(i-1)s(i-1,j)$$
根据递推式不难发现 $s(i,j)$其实就是第一类斯特林数。
枚举 $n$放哪不难得到 $$ans=sum_{i=1}^ns(i-1,a-1)*s(n-i,b-1)*C_{n-1}^{i-1}$$
但这样子显然没法求，考虑继续化简。
设前缀最大值的位置为 $p_1,p_2,...,p_a$，我们可以把 $[p_i,p_{i+1}-1]$看做一块，那么现在相当于要选 $a+b-2$块出来，然后选出 $a-1$块放到 $n$前面，其余放$n$后面，那么答案就是 $$s(n-1,a+b-2)*C_{a+b-2}^{a-1}$$
很好，那么现在我们就只要求一个第一类斯特林数就好了。怎么求呢？
其实第一类斯特林数 $s(n,m)$就等于 $x$的$n$次上升幂的第m项系数，这个根据递推式不难证明。
直接用分治FFT来求就好了。
复杂度 $O(nlog^2n)$。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

typedef long long LL;

const int N=200005;
const int MOD=998244353;

int n,p,q,a[20][N],rev[N],L;

int ksm(int x,int y)
{
    int ans=1;
    while (y)
    {
        if (y&1) ans=(LL)ans*x%MOD;
        x=(LL)x*x%MOD;y>>=1;
    }
    return ans;
}

void NTT(int *a,int f)
{
    for (int i=0;i<L;i++) if (i<rev[i]) std::swap(a[i],a[rev[i]]);
    for (int i=1;i<L;i<<=1)
    {
        int wn=ksm(3,f==1?(MOD-1)/i/2:MOD-1-(MOD-1)/i/2);
        for (int j=0;j<L;j+=(i<<1))
        {
            int w=1;
            for (int k=0;k<i;k++)
            {
                int u=a[j+k],v=(LL)a[j+k+i]*w%MOD;
                a[j+k]=(u+v)%MOD;a[j+k+i]=(u+MOD-v)%MOD;
                w=(LL)w*wn%MOD;
            }
        }
    }
    int ny=ksm(L,MOD-2);
    if (f==-1) for (int i=0;i<L;i++) a[i]=(LL)a[i]*ny%MOD;
}

void solve(int l,int r,int d)
{
    if (l==r) {a[d][0]=l;a[d][1]=1;return;}
    int mid=(l+r)/2;
    solve(l,mid,d+1);
    for (int i=0;i<=mid-l+1;i++) a[d][i]=a[d+1][i];
    solve(mid+1,r,d+1);
    int lg=0;
    for (L=1;L<=r-l+1;L<<=1,lg++);
    for (int i=0;i<L;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
    for (int i=mid-l+2;i<L;i++) a[d][i]=0;
    for (int i=r-mid+1;i<L;i++) a[d+1][i]=0;
    NTT(a[d],1);NTT(a[d+1],1);
    for (int i=0;i<L;i++) a[d][i]=(LL)a[d][i]*a[d+1][i]%MOD;
    NTT(a[d],-1);
}

int C(int n,int m)
{
    int ans=1,s=1;
    for (int i=0;i<m;i++) ans=(LL)ans*(n-i)%MOD,s=(LL)s*(i+1)%MOD;
    return (LL)ans*ksm(s,MOD-2)%MOD;
}

int main()
{
    scanf("%d%d%d",&n,&p,&q);
    if (p+q-2>n-1||!p||!q) {puts("0");return 0;}
    if (n==1) {puts("1");return 0;}
    solve(0,n-2,0);
    printf("%d",(LL)a[0][p+q-2]*C(p+q-2,p-1)%MOD);
    return 0;
}

最后

以上就是丰富银耳汤为你收集整理的Codeforces 960G Bandit Blues 第一类斯特林数+分治FFT题意分析代码的全部内容，希望文章能够帮你解决Codeforces 960G Bandit Blues 第一类斯特林数+分治FFT题意分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。