C++14(g++5.4) 解法, 执行用时: 43ms, 内存消耗: 13164K, 提交时间: 2020-06-19 19:50:08

#include <bits/stdc++.h>

const int moder = 998244353;
const int N = 1000010;

char s[N];
int fac[N], inv[N], invf[N];

void add(int &a, int b){
    a += b;
    a -= a >= moder ? moder : 0;
}

int main(){
    int n;
    scanf("%d%s", &n, s);
    fac[0] = invf[0] = 1;
    for (int i = 1; i < N; ++ i){
        fac[i] = 1ll * fac[i - 1] * i % moder;
        inv[i] = i == 1 ? 1 : moder - 1ll * (moder / i) * inv[moder % i] % moder;
        invf[i] = 1ll * invf[i - 1] * inv[i] % moder;
    }
    if (s[0] == '2'){
        puts("1");
        return 0;
    }
    int ans = 0, prod = 1, prob = 1;
    int cnt = 0;
    for (int i = 0; i < n; ++ i){
        add(ans, prob);
        if (s[i] == '2'){
            prod = 1ll * prod * (i - cnt) % moder;
            ++ cnt;
            prob = 1ll * prod * fac[n - cnt] % moder * invf[n] % moder;
        }
    }
    printf("%d\n", ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 10284K, 提交时间: 2020-06-24 08:38:00

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=998244353;
int n;
ll f[N];
char s[N];
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
int main()
{
    f[0]=1;for(int i=1;i<N;i++) f[i]=f[i-1]*i%mod;
    scanf("%d",&n);
    scanf("%s",s+1);
    int k=0;
    ll p=1,ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+p*f[n-k])%mod;
        if(s[i]=='2')
        {
            p=p*(i-1-k)%mod;
            k++;
        }
    }
    printf("%lld\n",ans*qpow(f[n],mod-2)%mod);
}