Advertisement
999ms

Untitled

Nov 11th, 2019
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. const ll mod = 998244353;
  8.  
  9. const int N = 202;
  10.  
  11. ll fact[N];
  12. ll invfact[N];
  13.  
  14. ll fastPow(ll a, ll p) {
  15.     ll ans = 1;
  16.     while (p) {
  17.         if (p & 1) {
  18.             ans *= a;
  19.             ans %= mod;
  20.         }
  21.         a *= a;
  22.         a %= mod;
  23.         p >>= 1;
  24.     }
  25.     return ans;
  26. }
  27.  
  28. ll C(int n, int m) {
  29.     if (n < m) return 0;
  30.     ll ans = fact[n] * invfact[m] % mod;
  31.     return ans * invfact[n - m] % mod;
  32. }
  33.  
  34. int Bit(int x, int i) {
  35.     return (x >> i) & 1;
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.     cout.tie(nullptr);
  42.     fact[0] = 1;
  43.     invfact[0] = 1;
  44.     for (int i = 1; i < N; i++) {
  45.         fact[i] = fact[i - 1] * i % mod;
  46.         invfact[i] = fastPow(fact[i], mod - 2);
  47.     }
  48.     int n;
  49.     cin >> n;
  50.     /*
  51.     vector<int> arr(n);
  52.     iota(all(arr), 0);
  53.     int itr = 0;
  54.     do {
  55.         for (int mask = 0; mask < (1 << n); mask++) {
  56.             int bad = 0;
  57.             for (int i = 0; i < n; i++) {
  58.                 if (!Bit(mask, i)) {
  59.                     if (arr[i] == i) {
  60.                         bad++;
  61.                     }
  62.                 }
  63.             }
  64.             if (bad) {
  65.                 itr++;
  66.                 int f = 0;
  67.                 for (int i = 0; i < n; i++) {
  68.                     f += abs(arr[i]) == i;
  69.                 }
  70.                 cout << itr << ": " << f << " = ";
  71.                 for (int i = 0; i < n; i++) {
  72.                     if (Bit(mask, i)) {
  73.                         cout << -arr[i] - 1 << " ";
  74.                     } else {
  75.                         cout << arr[i] + 1 << " ";
  76.                     }
  77.                 }
  78.                 cout << "\n";
  79.             }
  80.         }
  81.     } while (next_permutation(all(arr)));
  82.     */
  83.     ll tot = 0;
  84.     ll ans = fastPow(2, n) * fact[n] % mod;
  85.     for (int i = 1; i <= n; i++) {
  86.         if (i == n - 1) continue;
  87.         ll a = C(n, i);
  88.         a *= fastPow(2, i) - 1;
  89.         a %= mod;
  90.         if (i != n) {
  91.             int k = n - i;
  92.             ll dlt = fact[k];
  93.             for (int j = 1; j <= k; j++) {
  94.                 if (j & 1) {
  95.                     dlt -= fact[k] * invfact[j] % mod;
  96.                 } else {
  97.                     dlt += fact[k] * invfact[j] % mod;
  98.                 }
  99.                 dlt %= mod;
  100.                 if (dlt < 0) dlt += mod;
  101.             }
  102.             //cout << k << " " << dlt << endl;
  103.             a *= dlt;
  104.             a %= mod;
  105.         }
  106.         a *= fastPow(2, n - i);
  107.         a %= mod;
  108.         ans -= a;
  109.         tot += a;
  110.         //cout << "equals : " << i << " val : " <<  a << "\n";
  111.         if (ans < 0) ans += mod;
  112.     }
  113.     //cout << tot << endl;
  114.  
  115.     cout << ans << endl;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement