999ms

Untitled

Nov 27th, 2021
750
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(),(x).end()
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. const ll mod = 998244353;
  9.  
  10. ll fpow(ll a, ll p) {
  11.     ll ans = 1;
  12.     while (p) {
  13.         if (p & 1) {
  14.             ans = (ans * a) % mod;
  15.         }
  16.         a = (a * a) % mod;
  17.         p >>= 1;
  18.     }
  19.     return ans;
  20. }
  21.  
  22. vector<ll> facts = {1};
  23.  
  24. ll Fact(int n) {
  25.     while (facts.size() <= n) {
  26.         facts.push_back(facts.back() * facts.size() % mod);
  27.     }
  28.     return facts[n];
  29. }
  30.  
  31. vector<ll> rev = {1};
  32.  
  33. ll Rev(int n) {
  34.     while (rev.size() <= n) {
  35.         rev.push_back(rev.back() * fpow(rev.size(), mod - 2) % mod);
  36.     }
  37.     return rev[n];
  38. }
  39.  
  40. ll C(int n, int m) {
  41.     return (Fact(n) * Rev(m) % mod) * Rev(n - m) % mod;
  42. }
  43.  
  44. ll CaclProb(int k, int n, int a, int b) {
  45.     ll revB = fpow(b, mod - 2);
  46.     ll p = a * revB % mod;
  47.     ll res = C(n, k) * fpow(p, k) % mod;
  48.     ll tmp = fpow((mod + b - a) * fpow(b, mod - 2) % mod, n - k);
  49.     res = (res * tmp) % mod;
  50.     ll tot = fpow(2, n);
  51.     res = (res * fpow(tot, mod - 2)) % mod;
  52.     return res;
  53. }
  54.  
  55. void solve() {
  56.     int n, a, b;
  57.     cin >> n >> a >> b;
  58.     vector<ll> ans(n + 1);
  59.     ll tot = fpow(n - 1, n);
  60.     ll totRev = fpow(tot, mod - 2);
  61.     for (int k = 0; k <= n; k++) {
  62.         // number of shoots
  63.         ll cur = CaclProb(k, n, a, b);
  64.         cout << k << ' ' << n << ' ' << cur << endl;
  65.         for (int dead = (k > 0); dead <= k; dead++) {
  66.             ll num = C(n, dead) * C(k, dead) % mod;
  67.             ll curProb = num * totRev % mod;
  68.             curProb *= cur;
  69.             curProb %= mod;
  70.             ans[n - dead] += curProb;
  71.             ans[n - dead] %= mod;
  72.         }
  73.     }
  74.  
  75.     for (auto val: ans) {
  76.         cout << val << '\n';
  77.     }
  78. }
  79.  
  80. int main() {
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.     cout.tie(nullptr);
  84.     solve();
  85. }
  86.  
RAW Paste Data