結果

問題 No.1195 数え上げを愛したい（文字列編）
ユーザー snow39snow39
提出日時 2020-09-02 16:42:53
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,295 ms / 3,000 ms
コード長 3,564 bytes
コンパイル時間 1,290 ms
コンパイル使用メモリ 102,764 KB
実行使用メモリ 31,272 KB
最終ジャッジ日時 2024-11-21 14:30:17
合計ジャッジ時間 33,412 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,294 ms
31,152 KB
testcase_01 AC 2,293 ms
31,176 KB
testcase_02 AC 2,295 ms
31,092 KB
testcase_03 AC 215 ms
15,552 KB
testcase_04 AC 263 ms
15,836 KB
testcase_05 AC 229 ms
25,064 KB
testcase_06 AC 14 ms
10,328 KB
testcase_07 AC 13 ms
10,496 KB
testcase_08 AC 384 ms
12,624 KB
testcase_09 AC 2,185 ms
31,060 KB
testcase_10 AC 1,235 ms
20,656 KB
testcase_11 AC 1,992 ms
31,080 KB
testcase_12 AC 1,835 ms
29,032 KB
testcase_13 AC 1,553 ms
20,848 KB
testcase_14 AC 964 ms
20,756 KB
testcase_15 AC 1,184 ms
20,652 KB
testcase_16 AC 1,049 ms
20,632 KB
testcase_17 AC 404 ms
12,752 KB
testcase_18 AC 1,889 ms
27,160 KB
testcase_19 AC 1,835 ms
29,064 KB
testcase_20 AC 1,579 ms
20,852 KB
testcase_21 AC 2,008 ms
31,272 KB
testcase_22 AC 1,502 ms
20,832 KB
testcase_23 AC 14 ms
10,328 KB
testcase_24 AC 13 ms
10,496 KB
testcase_25 AC 13 ms
10,496 KB
権限があれば一括ダウンロードができます

ソースコード

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(const vector<ll> &a,const vector<ll> &b){
    int size=a.size()+b.size()-1;
    int n=1;
    while(n<size) n<<=1;

    vector<ll> A(n,0),B(n,0);
    for(int i=0;i<a.size();i++) A[i]=a[i];
    for(int i=0;i<b.size();i++) B[i]=b[i];

    /*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