結果

問題 No.1195 数え上げを愛したい（文字列編）
コンテスト
ユーザー snow39
提出日時 2020-09-02 16:39:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,274 ms / 3,000 ms
コード長 3,429 bytes
コンパイル時間 1,158 ms
コンパイル使用メモリ 104,924 KB
実行使用メモリ 33,372 KB
最終ジャッジ日時 2024-11-21 14:29:33
合計ジャッジ時間 33,462 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=998244353;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

#define MAX_N 300003
ll inv[MAX_N+10],fac[MAX_N+10],ifac[MAX_N+10];

void setComb(){
  inv[0]=1;inv[1]=1;fac[1]=1;ifac[1]=1;fac[0]=1;ifac[0]=1;
  for(int i=2;i<MAX_N;++i){
    inv[i]=(-MOD/i)*inv[MOD%i]%MOD;
    fac[i]=fac[i-1]*i%MOD;
    ifac[i]=ifac[i-1]*inv[i]%MOD;

    inv[i]=(inv[i]+MOD)%MOD;
    fac[i]=(fac[i]+MOD)%MOD;
    ifac[i]=(ifac[i]+MOD)%MOD;
  }
  return;
}

ll comb(ll n,ll k){
  if(n<k||n<0||k<0) return 0;
  else return ((fac[n]*ifac[k]%MOD*ifac[n-k]%MOD+MOD)%MOD);
}

ll hcomb(ll n,ll r){// this size is really ok??
  if(n==0&&r==0) return 1;
  else if(n<0||r<0) return 0;
  else return comb(n+r-1,r);
}

ll mod_pow(ll x,ll n){
  x%=MOD;
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%MOD;
    x=x*x%MOD;
    n>>=1;
  }
  return res;
}

ll mod_inverse(ll x){
  return mod_pow(x,MOD-2);
}

void add(ll &a,ll b){
  a=(a+b)%MOD;
}

void mul(ll &a,ll b){
  a%=MOD;b%=MOD;
  a=a*b%MOD;
}

//const ll MOD=998244353; // MOD == 119*2^23+1
//depends on mod_pow,mod_inverse

ll root[24],invroot[24];

void NTT_init(){
    for(int i=0;i<24;++i){
        root[i]=mod_pow(3,(MOD-1)/(1<<i));
        invroot[i]=mod_inverse(root[i]);
    }
}

vector<ll> NTT(vector<ll> a,bool inverse=false){
    int n=a.size();
    int high=0;
    for(int i=0;(1<<i)<n;++i) high++;

    for(int i=0;i<n;++i){
        int mask=0;
        for(int k=0;k<high;++k){
            if(i>>k&1) mask|=(1<<(high-1-k));
        }
        if(i<mask) swap(a[i],a[mask]);
    }

    for(int j=1;(1<<j)<=n;++j){
        int m=(1<<j);
        ll zeta=root[j];
        if(inverse) zeta=invroot[j];
        for(int i=0;i<n;i+=m){
            ll powzeta=1;
            for(int k=i;k<i+m/2;++k){
                ll s=a[k];
                ll t=a[k+m/2]*powzeta%MOD;

                a[k]=(s+t)%MOD;
                //while(a[k]>=MOD) a[k]-=MOD;
                a[k+m/2]=(s-t+MOD)%MOD;
                //while(a[k+m/2]>=MOD) a[k+m/2]-=MOD;
                powzeta=powzeta*zeta%MOD;
            }
        }
    }

    if(inverse){
        ll invn=mod_inverse(n);
        for(int i=0;i<n;++i) a[i]=a[i]*invn%MOD;
    }
    return a;
}

vector<ll> convolute(vector<ll> A,vector<ll> B){
    int size=A.size()+B.size()-1;
    int n=1;
    while(n<size) n<<=1;

    A.resize(n);
    B.resize(n);

    A=NTT(A);
    B=NTT(B);

    for(int i=0;i<n;++i) A[i]=A[i]*B[i]%MOD;
    A=NTT(A,true);

    A.resize(size);
    return A;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S;
  cin>>S;
  int N=S.size();

  vector<ll> alp(26,0);
  rep(i,N) ++alp[S[i]-'a'];
  sort(all(alp));

  setComb();

  NTT_init();

  vector<ll> ans={1};
  for(int k=0;k<26;++k){
    if(alp[k]==0) continue;

    vector<ll> A(alp[k]+1);
    for(int j=0;j<=alp[k];++j) A[j]=ifac[j];
    ans=convolute(ans,A);
  }
  for(int i=0;i<ans.size();++i) ans[i]=ans[i]*fac[i]%MOD;

  ll result=0;
  for(int i=1;i<ans.size();++i) result=(result+ans[i])%MOD;
  cout<<result<<"\n";

  return 0;
}
0