Luogu P4609 [FJOI2016]建筑师&&CF 960G Bandit Blues

考虑转化题意，我们发现其实就是找一个长度为\(n\)的全排列，使得这个排列有\(A\)个前缀最大值，\(B\)个后缀最大值，求方案数

我们考虑把最大值拎出来单独考虑，同时定义一些数的顺序排列为单调块（随便取的名字）

考虑在这个最大值左边有\(A-1\)个单调块，右边有\(B-1\)个单调块，如果这些块在左右两边按序排好的话就是一种合法方案

那我们只需要找出\(A+B-2\)个单调块，并且将其中拿出\(A-1\)个放在左边，因此答案有一项就是\(C_{A+B-2}^{A-1}\)

考虑怎么从除了最大值外的\(n-1\)个数里挑出单调块，我们仔细分析一下，发现单调块的个数其实就是圆排列的个数

因为对于任意一个圆排列\(a_1,a_2,\cdots,a_k\)，我们必然可以拿出其中的最大值\(a_{mx}\)，然后\(a_{mx},a_{mx+1},a_k,\cdots,a_1,a_{mx-1}\)就是一个单调块

不难发现这种关系唯一对应，所以答案已经出来了，就是\([_{A+B-2}^{n-1}]\cdot C_{A+B-2}^{A-1}\)

那么对于Luogu P4609 [FJOI2016]建筑师我们\(O(n^2)\)预处理出第一类斯特林数和组合数的值，然后\(O(1)\)计算就好了

CODE

#include<cstdio>

#define RI register int

#define CI const int&

using namespace std;

const int N=50000,M=200,mod=1e9+7;

int t,n,a,b,C[M+5][M+5],s[N+5][M+5];

inline int sum(CI a,CI b)

{

	int t=a+b; return t>=mod?t-mod:t;

}

inline int min(CI a,CI b)

{

	return a<b?a:b;

}

inline void init(void)

{

	RI i,j; for (s[0][0]=i=1;i<=N;++i) for (j=min(i,M);j;--j)

	s[i][j]=sum(s[i-1][j-1],1LL*(i-1)*s[i-1][j]%mod);

	for (i=0;i<=M;++i) for (C[i][0]=C[i][i]=j=1;j<i;++j)

	C[i][j]=sum(C[i-1][j],C[i-1][j-1]);

}

int main()

{

	for (init(),scanf("%d",&t);t;--t)

	{

		scanf("%d%d%d",&n,&a,&b); if (!a||!b||n-1<a+b-2) { puts("0"); continue; }

		printf("%d\n",1LL*s[n-1][a+b-2]*C[a+b-2][a-1]%mod);

	}

	return 0;

}

考虑对于CF960G Bandit Blues 显然我们不能暴力求出所有的斯特林数，而是只求出一个即可

但是对于一个我们也没有太好的公式去算，因此我们类似于第二类斯特林数，可以用生成函数来算出一行的值

通过数学推导或者OIES，我们得到了第一类斯特林数的生成函数：

\[S_n=\prod_{i=0}^{n-1}(x+i)
\]

最后\(x^k\)的系数就是\([^n_k]\)，用分治NTT做到\(O(n\log^2 n)\)。有\(n\log n\)的做法但懒得写了（分治NTT实在好写）

CODE

#include<cstdio>

#include<vector>

#include<algorithm>

#define RI register int

#define CI const int&

#define pb push_back

using namespace std;

typedef vector <int> VT;

const int N=100005,mod=998244353;

int n,a,b;

inline int fact(CI n,int ret=1)

{

    for (RI i=1;i<=n;++i) ret=1LL*ret*i%mod; return ret;

}

inline int quick_pow(int x,int p=mod-2,int mul=1)

{

    for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;

}

inline int C(CI n,CI m)

{

    return 1LL*fact(n)*quick_pow(1LL*fact(m)*fact(n-m)%mod)%mod;

}

class Poly_Solver

{

    private:

        int rev[N<<2],lim,p;

        inline int sum(CI a,CI b)

        {

            int t=a+b; return t>=mod?t-mod:t;

        }

        inline int sub(CI a,CI b)

        {

            int t=a-b; return t<0?t+mod:t;

        }

        inline void swap(int& x,int& y)

        {

            int t=x; x=y; y=t;

        }

        inline void init(CI n)

        {

            for (lim=1,p=0;lim<=n;lim<<=1,++p);

            for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);

        }

        inline void NTT(int *f,CI opt)

        {

            RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);

            for (i=1;i<lim;i<<=1)

            {

                int m=i<<1,D=quick_pow(3,~opt?(mod-1)/m:mod-1-(mod-1)/m);

                for (RI j=0;j<lim;j+=m)

                {

                    int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)

                    {

                        int x=f[j+k],y=1LL*f[i+j+k]*W%mod;

                        f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);

                    }

                }

            }

            if (!~opt)

            {

                int Inv=quick_pow(lim); for (RI i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;

            }

        }

        inline VT merge(const VT& VA,const VT& VB)

        {

            static int A[N<<2],B[N<<2],n,m; VT VC; RI i;

            for (n=VA.size(),i=0;i<n;++i) A[i]=VA[i];

            for (m=VB.size(),i=0;i<m;++i) B[i]=VB[i];

            init(n+m); fill(A+n,A+lim,0); fill(B+m,B+lim,0);

            for (NTT(A,1),NTT(B,1),i=0;i<lim;++i) A[i]=1LL*A[i]*B[i]%mod;

            for (NTT(A,-1),i=0;i<n+m-1;++i) VC.pb(A[i]); return VC;

        }

    public:

        inline VT solve(CI l,CI r)

        {

            VT p; if (l==r) return p.pb(l),p.pb(1),p;

            int mid=l+r>>1; return merge(solve(l,mid),solve(mid+1,r));

        }

}P;

int main()

{

    scanf("%d%d%d",&n,&a,&b); if (!a||!b||n-1<a+b-2) return puts("0"),0;

    if (n==1) return puts("1"),0; VT ans=P.solve(0,n-2);

    return printf("%d",1LL*ans[a+b-2]*C(a+b-2,a-1)%mod),0;

}

巴特西

Luogu P4609 [FJOI2016]建筑师&&CF 960G Bandit Blues

最新文章

热门文章