Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- using ll = long long;
- const ll mod = 998244353;
- const int N = 202;
- ll fact[N];
- ll invfact[N];
- ll fastPow(ll a, ll p) {
- ll ans = 1;
- while (p) {
- if (p & 1) {
- ans *= a;
- ans %= mod;
- }
- a *= a;
- a %= mod;
- p >>= 1;
- }
- return ans;
- }
- ll C(int n, int m) {
- if (n < m) return 0;
- ll ans = fact[n] * invfact[m] % mod;
- return ans * invfact[n - m] % mod;
- }
- int Bit(int x, int i) {
- return (x >> i) & 1;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- fact[0] = 1;
- invfact[0] = 1;
- for (int i = 1; i < N; i++) {
- fact[i] = fact[i - 1] * i % mod;
- invfact[i] = fastPow(fact[i], mod - 2);
- }
- int n;
- cin >> n;
- /*
- vector<int> arr(n);
- iota(all(arr), 0);
- int itr = 0;
- do {
- for (int mask = 0; mask < (1 << n); mask++) {
- int bad = 0;
- for (int i = 0; i < n; i++) {
- if (!Bit(mask, i)) {
- if (arr[i] == i) {
- bad++;
- }
- }
- }
- if (bad) {
- itr++;
- int f = 0;
- for (int i = 0; i < n; i++) {
- f += abs(arr[i]) == i;
- }
- cout << itr << ": " << f << " = ";
- for (int i = 0; i < n; i++) {
- if (Bit(mask, i)) {
- cout << -arr[i] - 1 << " ";
- } else {
- cout << arr[i] + 1 << " ";
- }
- }
- cout << "\n";
- }
- }
- } while (next_permutation(all(arr)));
- */
- ll tot = 0;
- ll ans = fastPow(2, n) * fact[n] % mod;
- for (int i = 1; i <= n; i++) {
- if (i == n - 1) continue;
- ll a = C(n, i);
- a *= fastPow(2, i) - 1;
- a %= mod;
- if (i != n) {
- int k = n - i;
- ll dlt = fact[k];
- for (int j = 1; j <= k; j++) {
- if (j & 1) {
- dlt -= fact[k] * invfact[j] % mod;
- } else {
- dlt += fact[k] * invfact[j] % mod;
- }
- dlt %= mod;
- if (dlt < 0) dlt += mod;
- }
- //cout << k << " " << dlt << endl;
- a *= dlt;
- a %= mod;
- }
- a *= fastPow(2, n - i);
- a %= mod;
- ans -= a;
- tot += a;
- //cout << "equals : " << i << " val : " << a << "\n";
- if (ans < 0) ans += mod;
- }
- //cout << tot << endl;
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement