fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 998244353;
  4.  
  5. inline int addmod(int a, int b) {
  6.     int res = a + b;
  7.     if (res >= MOD) res -= MOD;
  8.     return res;
  9. }
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     int N;
  16.     string T;
  17.     cin >> N >> T;
  18.  
  19.     int total = 1 << N;
  20.     vector<int> dp(total, 0);
  21.     dp[0] = 1;
  22.  
  23.     // 각 알파벳마다 등장 인덱스를 저장
  24.     vector<vector<int>> pos(26);
  25.     for (int i = 0; i < N; i++) {
  26.         pos[T[i] - 'a'].push_back(i);
  27.     }
  28.  
  29.     for (int mask = 0; mask < total; mask++) {
  30.         if (!dp[mask]) continue;
  31.         int len = __builtin_popcount(mask);
  32.  
  33.         // 새로운 문자 하나 선택
  34.         for (int j = 0; j < N; j++) {
  35.             if (mask & (1 << j)) continue; // 이미 선택된 문자 skip
  36.  
  37.             // 같은 문자 오름차순 제약
  38.             bool ok = true;
  39.             for (int prev : pos[T[j] - 'a']) {
  40.                 if (prev < j && !(mask & (1 << prev))) {
  41.                     ok = false; // 이전 동일 문자가 아직 추가 안됨
  42.                     break;
  43.                 }
  44.             }
  45.             if (!ok) continue;
  46.  
  47.             int newMask = mask | (1 << j);
  48.             dp[newMask] = addmod(dp[newMask], (int)((1LL * dp[mask] * (len + 1)) % MOD));
  49.         }
  50.     }
  51.  
  52.     cout << dp[total - 1] << "\n";
  53.     return 0;
  54. }
Success #stdin #stdout 0.04s 19696KB
comments (?)
stdin
copy 
22
atcoderbeginnercontest
stdout
copy 
886184150
https://ideone.com/KvdqTE
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!