Submission #45023731

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
using namespace atcoder;

const int MAXN = 2e5+10,LIM = 4e5+5;

using mint = modint998244353;
typedef vector<mint> Poly;

int n,p,a[MAXN],pre[MAXN];
string s;

mint f[MAXN],g[MAXN],ans;
mint fac[MAXN*2],rfac[MAXN*2];

int main(){
	cin>>s;n = s.length();
	rep(i,1,n)a[i] = s[i-1] - '0';
	for(p=1;p<n && a[p] <= a[p+1];p++);

	fac[0] = 1;rep(i,1,LIM)fac[i] = fac[i-1] * i;
	rep(i,0,LIM)rfac[i] = fac[i].inv();

	pre[p] = 100;rep(i,p+1,n)pre[i] = min(pre[i-1],a[i]);
	if(pre[n] <= a[1]){cout<<"0\n";exit(0);}

	f[n] = 1;
	for(int l=1,r,len,q=n;l<=p;l=r+1){
		for(r=l,len=1;r<p&&a[r+1]==a[l];r++,len++);
		rep(i,l,r-1)ans += f[i];
		for(int i=r,mn=100,cnt=0;i<=n && mn>a[l];i++,mn=min(mn,a[i]),cnt++){
			mint C = fac[cnt+len-1] * rfac[len-1] * rfac[cnt];
			ans += f[i] * C;
		}
		//
		while(q>=p && pre[q] <= a[l])q--;

		
		Poly A(n+1,0),B(n+1,0);
		rep(i,r+1,q)A[i] = f[i];
		rep(i,0,n)B[n-i] = fac[i+len-1] * rfac[i];
		A = convolution(A,B);
		rep(i,r+1,q)f[i] = A[n+i] * rfac[len-1];
	}

	cout<<ans.val()<<endl;
    return 0;
}

Submission Info

Judge Result