結果

問題 No.1195 数え上げを愛したい（文字列編）
ユーザー snow39snow39
提出日時 2020-09-02 15:50:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,969 bytes
コンパイル時間 1,196 ms
コンパイル使用メモリ 103,800 KB
実行使用メモリ 77,792 KB
最終ジャッジ日時 2024-11-21 14:12:52
合計ジャッジ時間 57,986 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 AC 403 ms
31,668 KB
testcase_04 AC 491 ms
32,056 KB
testcase_05 AC 389 ms
41,448 KB
testcase_06 AC 57 ms
26,784 KB
testcase_07 AC 55 ms
26,840 KB
testcase_08 AC 677 ms
29,164 KB
testcase_09 TLE -
testcase_10 AC 2,145 ms
36,148 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 AC 2,709 ms
36,548 KB
testcase_14 AC 1,698 ms
36,124 KB
testcase_15 AC 2,066 ms
37,744 KB
testcase_16 AC 1,829 ms
37,724 KB
testcase_17 AC 710 ms
29,316 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 AC 2,753 ms
36,632 KB
testcase_21 TLE -
testcase_22 AC 2,623 ms
36,456 KB
testcase_23 AC 54 ms
26,748 KB
testcase_24 AC 55 ms
26,776 KB
testcase_25 AC 57 ms
77,792 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 1000010
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;
                while(a[k]>=MOD) a[k]-=MOD;
                a[k+m/2]=s-t+MOD;
                while(a[k+m/2]>=MOD) a[k+m/2]-=MOD;
                (powzeta*=zeta)%=MOD;
            }
        }
    }

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

                a[k+j]=s+t;
                while(a[k+j]>=MOD) a[k+j]-=MOD;
                a[k+j+b]=s-t+MOD;
                while(a[k+j+b]>=MOD) a[k+j+b]-=MOD;
            }
        }
    }*/

    if(inverse){
        ll invn=mod_inverse(n);
        for(int i=0;i<n;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*=2;

    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=NTT(A);
    B=NTT(B);

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

    vector<ll> res(size);
    for(int i=0;i<size;i++) res[i]=A[i];
    return res;
}

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++) mul(ans[i],fac[i]);

  ll result=0;
  for(int i=1;i<ans.size();i++) add(result,ans[i]);
  cout<<result<<endl;

  return 0;
}
0