题目概述

LOJ575

解题报告

有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前缀和后缀和是没有办法加速的，复杂度只能是 $O(n^2)$ 。

这种相邻元素的限制关系，可以考虑序列容斥，定义 $f_i$ 表示前 $i$ 个位置合法的方案数（但不管 $i$ 和 $i+1$ 的限制）。由于相连的一段<对应着一个递增序列，我们先找到 $i$ 前面的第一个 $s_j='>'$ ，不考虑 $j$ 和 $j+1$ 的限制，则方案数很容易计算：

$$ f_i={i\choose i-j}f_j $$

即，先选出 $i-j$ 个数放到后面构成递增序列，剩下的合法方案数为 $f_j$ 。

因为这样没考虑 $j$ 和 $j+1$ 的限制，所以找到 $j$ 前面的>位置 $k$ ，强制 $k+1$ 到 $i$ 均为<，以扣除 $j$ 和 $j+1$ 的限制，以此类推构成序列容斥（记录 $sum_i$ 表示前 $i$ 个>的数量，为了方便，认为 $s_0='>'$ ，且 $f_0=1$ ）：

$$ f_i=\sum_{j=0}^{i-1}[s_j='>'](-1)^{sum_{i-1}-sum_j}{i\choose i-j}f_j $$

不难发现是一个分治NTT的形式。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=1<<17,MOD=998244353;

int n,cnt[maxn+5],f[maxn+5],g[maxn+5];char s[maxn+5];
int INV[maxn+5],fac[maxn+5],wn[maxt+5],A[maxt+5],B[maxt+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=MUL(fac[i-1],i),INV[i]=MUL(INV[i-1],INV[i]);
}
void Solve(int L,int R){
    if (L==R){
        L && cnt[L-1]?f[L]=MUL(f[L],cnt[L-1]&1?MOD-1:1):f[L]=INV[L];
        g[L]=(s[L]=='>')*MUL(f[L],cnt[L]&1?MOD-1:1);
        return;
    }
    int mid=L+(R-L>>1);
    Solve(L,mid);
    int t;for (t=1;t<=R-L;t<<=1);
    for (int i=L;i<=mid;i++) A[i-L]=g[i];for (int i=mid-L+1;i<t;i++) A[i]=0;
    B[0]=0;for (int i=1;i<=R-L;i++) B[i]=INV[i];for (int i=R-L+1;i<t;i++) B[i]=0;
    NTT(A,t,1);NTT(B,t,1);
    for (int i=0;i<t;i++) A[i]=MUL(A[i],B[i]);
    NTT(A,t,-1);for (int i=mid+1;i<=R;i++) f[i]=ADD(f[i],A[i-L]);
    Solve(mid+1,R);
}
int main(){
    scanf("%s",s+1);n=strlen(s+1)+1;Make(n);
    s[0]='>';cnt[0]=1;
    for (int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(s[i]=='>');
    if (!cnt[n]) {puts("1");return 0;}
    Solve(0,n);
    printf("%d\n",MUL(f[n],fac[n]));
    return 0;
}