fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 998244353;
  5.  
  6. int addmod(int a, int b) {
  7.     int res = a + b;
  8.     if (res >= MOD) res -= MOD;
  9.     return res;
  10. }
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.  
  16.     int N;
  17.     string T;
  18.     cin >> N >> T;
  19.  
  20.     int totalStates = 1 << N;
  21.     vector<int> dp(totalStates, 0);
  22.     dp[0] = 1;  // 초기 상태: 빈 문자열
  23.  
  24.     // 알파벳별로 인덱스 저장
  25.     vector<vector<int>> positions(26);
  26.     for (int i = 0; i < N; i++) {
  27.         positions[T[i] - 'a'].push_back(i);
  28.     }
  29.  
  30.     // 비트마스크 DP
  31.     for (int mask = 0; mask < totalStates; mask++) {
  32.         if (dp[mask] == 0) continue;
  33.         int len = __builtin_popcount(mask);
  34.  
  35.         // 다음으로 넣을 문자 결정
  36.         for (int i = 0; i < N; i++) {
  37.             if (mask & (1 << i)) continue; // 이미 포함된 문자면 skip
  38.  
  39.             // 중복 문자 처리:
  40.             // 같은 문자가 여러 개라면, 인덱스가 증가하는 순서로만 넣을 수 있도록
  41.             char c = T[i];
  42.             bool ok = true;
  43.             for (int idx : positions[c - 'a']) {
  44.                 if (idx < i && !(mask & (1 << idx))) {
  45.                     ok = false; // 앞의 같은 문자보다 먼저 추가되면 안됨
  46.                     break;
  47.                 }
  48.             }
  49.             if (!ok) continue;
  50.  
  51.             int newMask = mask | (1 << i);
  52.             dp[newMask] = addmod(dp[newMask], (int)((1LL * dp[mask] * (len + 1)) % MOD));
  53.         }
  54.     }
  55.  
  56.     cout << dp[totalStates - 1] << "\n";
  57.     return 0;
  58. }
Success #stdin #stdout 0.04s 19520KB
comments (?)
stdin 
22
atcoderbeginnercontest
stdout 
886184150
https://ideone.com/4fkAm0
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!