Submission #71152383

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int Maxn=2e6+7;
const int Mod=998244353;
char S[Maxn];
int cnt[Maxn][11];
int now[11];
ll val[Maxn];

ll fac[Maxn],ifac[Maxn];

inline ll ksm(ll a,int b,int mod){
    ll z=1;
    while(b){
        if(b&1) z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
inline ll Binom(int x,int y){
    if(y>x or x<0) return 0;
    return fac[x]*ifac[y]%Mod*ifac[x-y]%Mod; 
}

int main(){
    scanf("%s",S+1);
    int n=strlen(S+1);

    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%Mod;
    ifac[n]=ksm(fac[n],Mod-2,Mod);
    for(int i=n-1;~i;i--) ifac[i]=ifac[i+1]*(i+1)%Mod;

    for(int i=n;i;i--){
        for(int j=0;j<10;j++) cnt[i][j]=cnt[i+1][j];
        cnt[i][S[i]-'0']++;
    }

    ll ans=0;
    for(int i=1;i<=n;i++){
        int u=S[i]-'0';
        now[u]++;
        ans=(ans+Binom(now[u]+cnt[i+1][u+1]-1,now[u]))%Mod;
    }
    cout<<ans;

    return 0;
}

Submission Info

Judge Result