Advertisement
FlyingElephant

Untitled

Sep 2nd, 2023
240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define mt make_tuple
  4. #define pb push_back
  5. #define sz(a) (ll)(a).size()
  6. using namespace std;
  7. typedef long long ll;
  8. typedef long double lld;
  9. const ll mod = 998244353, N = 61;
  10. vector<ll> fact(N);
  11.  
  12. ll powmod(ll a, ll b, ll mod){
  13.     a %= mod;
  14.     if (a == 0) return 0;
  15.     ll product = 1;
  16.     while(b > 0){
  17.         if (b&1){
  18.             product *= a;
  19.             product %= mod;
  20.             --b;
  21.         }
  22.         a *= a;
  23.         a %= mod;
  24.         b /= 2;
  25.     }
  26.     return product;
  27. }
  28.  
  29. ll inverse(ll a, ll mod){
  30.     return powmod(a, mod-2, mod);
  31. }
  32.  
  33. ll nCk(ll n, ll k, ll mod){
  34.     return ((fact[n] * inverse(fact[k], mod) % mod) * inverse(fact[n-k], mod) % mod) % mod;
  35. }
  36.  
  37. void tc(){
  38.     ll n; cin >> n;
  39.     //draw partition
  40.     vector<ll> boris, alex;
  41.     for(ll i = n-1; i >= 1; i -= 4){
  42.         if(i >= 1){
  43.             alex.pb(i);
  44.         }
  45.         if(i-1 >= 1){
  46.             alex.pb(i-1);
  47.         }
  48.         if(i-2 >= 1){
  49.             boris.pb(i-2);
  50.         }
  51.         if(i-3 >= 1){
  52.             boris.pb(i-3);
  53.         }
  54.     }
  55.     sort(alex.begin(), alex.end());
  56.  
  57.     ll x = 0;
  58.     for(ll j = 1; j <= (n/2 - 2); ++j){
  59.         for(ll i = 0; i < sz(boris); ++i){
  60.             ll lb = lower_bound(alex.begin(), alex.end(), boris[i]) - alex.begin();
  61.             if(n/2 -2 -i < j -1 || lb < j){
  62.                 continue;
  63.             }
  64.             ll f1 = nCk(n/2 -2 -i, j-1, mod);
  65.             ll f2 = nCk(lb, j, mod);
  66.             ll p = (f1%mod*f2%mod)%mod;
  67.             x = (x%mod + p%mod)%mod;
  68.         }
  69.     }
  70.     ll half = nCk(n, n/2, mod)/2;
  71.     ll a = (half + x)%mod;
  72.     ll b = half%mod - x - 1;
  73.     if(b < 0){
  74.         b += mod;
  75.     }
  76.     cout << a << " " << b << " " << 1 << "\n";
  77. }
  78.  
  79. int main(){  
  80.     ios::sync_with_stdio(0);
  81.     cin.tie(0);
  82.    
  83.     fact[0] = 1;
  84.     for(ll i = 1; i < N; ++i){
  85.         fact[i] = ((fact[i-1]%mod)*(i%mod))%mod;
  86.     }
  87.    
  88.     ll t; cin >> t;
  89.     while(t--){
  90.         tc();
  91.     }
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement