fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 998244353;
  7. const int MAX = 500005;
  8.  
  9. long long fact[MAX];
  10. long long p2[MAX];
  11. long long inv[MAX];
  12.  
  13. void precompute() {
  14.     fact[0] = 1;
  15.     p2[0] = 1;
  16.     for (int i = 1; i < MAX; ++i) {
  17.         fact[i] = fact[i - 1] * i % MOD;
  18.         p2[i] = p2[i - 1] * 2 % MOD;
  19.     }
  20.     inv[1] = 1;
  21.     for (int i = 2; i < MAX; ++i) {
  22.         inv[i] = (MOD - 1LL * (MOD / i) * inv[MOD % i] % MOD) % MOD;
  23.     }
  24. }
  25.  
  26. void solve() {
  27.     int N, K;
  28.     cin >> N >> K;
  29.     vector<int> A(K);
  30.     vector<bool> in_A(N + 1, false);
  31.     int max_A = 0;
  32.     for (int i = 0; i < K; ++i) {
  33.         cin >> A[i];
  34.         in_A[A[i]] = true;
  35.         if (A[i] > max_A) {
  36.             max_A = A[i];
  37.         }
  38.     }
  39.  
  40.     long long ways = fact[N - K];
  41.     vector<long long> C(N + 1, 0);
  42.  
  43.     int running_max = 0;
  44.     for (int i = 0; i < K; ++i) {
  45.         int x = A[i];
  46.         if (running_max > x) {
  47.             C[x] = 0;
  48.         } else {
  49.             C[x] = ways;
  50.         }
  51.         if (x > running_max) {
  52.             running_max = x;
  53.         }
  54.     }
  55.  
  56.     for (int x = 1; x <= N; ++x) {
  57.         if (!in_A[x]) {
  58.             if (x < max_A) {
  59.                 C[x] = 0;
  60.             } else {
  61.                 C[x] = ways * inv[N - x + 1] % MOD;
  62.             }
  63.         }
  64.     }
  65.  
  66.     long long ans = 0;
  67.     for (int x = 1; x <= N; ++x) {
  68.         long long bad_ways = (ways - C[x] + MOD) % MOD;
  69.         long long term = p2[x - 1] * bad_ways % MOD;
  70.         ans = (ans + term) % MOD;
  71.     }
  72.  
  73.     cout << ans << "\n";
  74. }
  75.  
  76. int main() {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL);
  79.     precompute();
  80.     int T;
  81.     if (cin >> T) {
  82.         while (T--) {
  83.             solve();
  84.         }
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0.01s 15244KB
comments (?)
stdin
copy 
3
3 1
1
4 2
3 2
10 3
2 1 7
stdout
copy 
2
6
1382640
https://ideone.com/RGCWe7
language:
C++14 (gcc 8.3)
created:
5 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!