結果

問題 No.3178 free sort
ユーザー Rumain831
提出日時 2025-06-13 21:34:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 967 bytes
コンパイル時間 693 ms
コンパイル使用メモリ 79,336 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-13 21:34:50
合計ジャッジ時間 2,450 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

ll modpow(ll a, ll b, ll p){
  ll ans=1;
  while(b>0){
    if(b%2==1) ans=(ans*a)%p;
    b/=2;
    a=(a*a)%p;
  }
  return ans;
}

int main(void){
  string s; cin >> s;
  int n=s.size(), m=n;
  vector<ll> cnt(10), fact(2e5+2, 1), invfact(2e5+2, 1);
  ll mod=998244353;
  for(ll i=2; i<=2e5; i++) fact[i]=fact[i-1]*i%mod;
  invfact[2e5]=modpow(fact[2e5], mod-2, mod);
  for(ll i=2e5-1; i>=1; i--) invfact[i]=invfact[i+1]*(i+1)%mod;
  for(auto p:s) cnt[p-'0']++;
  ll ansall=1, lead0=1;
  for(int i=0; i<10; i++) ansall*=fact[m]*invfact[cnt[i]]%mod*invfact[m-cnt[i]]%mod, ansall%=mod, m-=cnt[i];
  m=n;
  if(cnt[0]){
    m--;
    cnt[0]--;
    for(int i=0; i<10; i++) lead0*=fact[m]*invfact[cnt[i]]%mod*invfact[m-cnt[i]]%mod, lead0%=mod, m-=cnt[i];
  }
  else lead0=0;
  //cout << ansall << ' ' << lead0 << endl;
  cout << (ansall-lead0+mod)%mod << endl;
  return 0; 
}
0