fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. static const int MOD = 998244353;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int T; 
  11.     if (!(cin >> T)) return 0;
  12.     while (T--) {
  13.         int n; 
  14.         cin >> n;
  15.         vector<int> a(n);
  16.         for (int i = 0; i < n; ++i) cin >> a[i];
  17.  
  18.         // Đếm tần suất
  19.         vector<int> cnt(n + 1, 0);
  20.         for (int x : a) cnt[x]++;
  21.         vector<int> freq;
  22.         int F = 0;
  23.         for (int x = 1; x <= n; ++x) if (cnt[x]) {
  24.             freq.push_back(cnt[x]);
  25.             F = max(F, cnt[x]);
  26.         }
  27.  
  28.         // DP: dp[j] = tổng tích f_x của các tập con có tổng tần suất = j
  29.         vector<int> dp(n + 1, 0);
  30.         dp[0] = 1;
  31.         for (int c : freq) {
  32.             for (int j = n - c; j >= 0; --j) {
  33.                 dp[j + c] = (dp[j + c] + (long long)dp[j] * c) % MOD;
  34.             }
  35.         }
  36.  
  37.         int ans = 0;
  38.         for (int j = F; j <= n; ++j) {
  39.             ans += dp[j];
  40.             if (ans >= MOD) ans -= MOD;
  41.         }
  42.         cout << ans << '\n';
  43.     }
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
5
3
1 2 3
3
1 1 1
3
1 2 2
10
1 1 1 1 2 2 2 3 3 4
10
1 1 1 2 2 2 3 3 3 4
stdout 
7
3
4
111
126
https://ideone.com/3MFh1R
language:
C++14 (gcc 8.3)
created:
8 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!