fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 998244353;
  8.  
  9. long long power(long long base, long long exp) {
  10.     long long res = 1;
  11.     base %= MOD;
  12.     while (exp > 0) {
  13.         if (exp % 2 == 1) res = res * base % MOD;
  14.         base = base * base % MOD;
  15.         exp /= 2;
  16.     }
  17.     return res;
  18. }
  19.  
  20. long long modInverse(long long n) {
  21.     return power(n, MOD - 2);
  22. }
  23.  
  24. const int MAXN = 105;
  25. long long fact[MAXN], invFact[MAXN];
  26.  
  27. void precompute() {
  28.     fact[0] = 1;
  29.     invFact[0] = 1;
  30.     for (int i = 1; i < MAXN; i++) {
  31.         fact[i] = fact[i - 1] * i % MOD;
  32.         invFact[i] = modInverse(fact[i]);
  33.     }
  34. }
  35.  
  36. void solve() {
  37.     int n;
  38.     long long c;
  39.     if (!(cin >> n >> c)) return;
  40.  
  41.     vector<long long> a(n + 1);
  42.     for (int i = 1; i <= n; i++) {
  43.         cin >> a[i];
  44.     }
  45.     sort(a.begin() + 1, a.end());
  46.  
  47.     vector<long long> w(n + 1);
  48.     for (int i = 1; i < n; i++) {
  49.         w[i] = (a[i + 1] - a[i]) % MOD;
  50.     }
  51.     w[n] = (c + 1 - a[n]) % MOD;
  52.     w[0] = (a[1] - 1) % MOD;
  53.  
  54.     vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
  55.     dp[0][0] = 1;
  56.  
  57.     for (int i = n; i >= 1; i--) {
  58.         vector<vector<long long>> next_dp(n + 1, vector<long long>(n + 1, 0));
  59.         long long current_w = w[i];
  60.  
  61.         vector<long long> w_pow(n + 1);
  62.         w_pow[0] = 1;
  63.         for (int p = 1; p <= n; p++) {
  64.             w_pow[p] = w_pow[p - 1] * current_w % MOD;
  65.         }
  66.  
  67.         for (int j = 0; j <= n; j++) {
  68.             for (int k = 0; k <= j; k++) {
  69.                 if (dp[j][k] == 0) continue;
  70.                 for (int m = 0; m <= n - j; m++) {
  71.                     int n_j = j + m;
  72.                     int n_k = k + m;
  73.                     if (n_k > 0) n_k--;
  74.                     long long term = dp[j][k] * w_pow[m] % MOD * invFact[m] % MOD;
  75.                     next_dp[n_j][n_k] = (next_dp[n_j][n_k] + term) % MOD;
  76.                 }
  77.             }
  78.         }
  79.         dp = next_dp;
  80.     }
  81.  
  82.     vector<long long> ans(n + 1, 0);
  83.     long long w0 = w[0];
  84.     vector<long long> w0_pow(n + 1);
  85.     w0_pow[0] = 1;
  86.     for (int p = 1; p <= n; p++) {
  87.         w0_pow[p] = w0_pow[p - 1] * w0 % MOD;
  88.     }
  89.  
  90.     for (int j = 0; j <= n; j++) {
  91.         for (int k = 0; k <= j; k++) {
  92.             if (dp[j][k] == 0) continue;
  93.             int matches = j - k;
  94.             int rem = n - j;
  95.             long long term = dp[j][k] * w0_pow[rem] % MOD * invFact[rem] % MOD;
  96.             ans[matches] = (ans[matches] + term) % MOD;
  97.         }
  98.     }
  99.  
  100.     long long prob_mult = fact[n] * modInverse(power(c, n)) % MOD;
  101.     for (int i = 0; i <= n; i++) {
  102.         long long final_ans = ans[i] * prob_mult % MOD;
  103.         cout << final_ans << (i == n ? "" : " ");
  104.     }
  105.     cout << "\n";
  106. }
  107.  
  108. int main() {
  109.     ios_base::sync_with_stdio(false);
  110.     cin.tie(NULL);
  111.     precompute();
  112.     int t;
  113.     if (cin >> t) {
  114.         while (t--) {
  115.             solve();
  116.         }
  117.     }
  118.     return 0;
  119. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
4
2 3
1 3
3 17
9 9 8
5 2025
1 1 1 1 1
6 1000
544 105 450 715 479 992
stdout
copy 
0 776412275 221832079
465698363 588015298 487439081 455335965
0 0 0 0 0 1
366062443 766314649 169448288 553531286 643499511 890090646 604030590
https://ideone.com/9fFFW3
language:
C++14 (gcc 8.3)
created:
6 hours 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!