Advertisement
Guest User

Untitled

a guest
Nov 28th, 2021
537
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(), (x).end()
  4. #define itn int
  5. #define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())
  6.  
  7. using namespace std;
  8.  
  9. inline int nxt() {
  10.     int x;
  11.     cin >> x;
  12.     return x;
  13. }
  14.  
  15. int mod;
  16.  
  17. const int N = 211'111;
  18.  
  19. long long inv[N], fact[N], invfact[N];
  20.  
  21. inline long long C(int n, int k) {
  22.     return fact[n] * invfact[k] % mod * invfact[n - k] % mod;
  23. }
  24.  
  25. long long ans[N];
  26.  
  27. int n;
  28. void rec(int sum, int mul, int cur, int cnt, int spent, long long val) {
  29.     if (sum + (n - spent) < mul) {
  30.         return;
  31.     }
  32.     if (sum + (n - spent) >= mul && sum < mul) {
  33.         ans[mul - sum + spent] += C(mul - sum + spent, spent) * val % mod;
  34.     }
  35.     while (sum + cur + n >= 1ll * cur * mul) {
  36.         rec(sum + cur, mul * cur, cur, cnt + 1, spent + 1, val * (spent + 1) % mod * inv[cnt + 1] % mod);
  37.         ++cur;
  38.         cnt = 0;
  39.     }
  40. }
  41.  
  42. int main() {
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(nullptr);
  45.  
  46.     n = nxt();
  47.     mod = nxt();
  48.     fact[0] = fact[1] = invfact[0] = invfact[1] = inv[1] = 1;
  49.     for (int i = 2; i <= n; ++i) {
  50.         inv[i] = mod - (mod / i) * inv[mod % i] % mod;
  51.         fact[i] = fact[i - 1] * i % mod;
  52.         invfact[i] = invfact[i - 1] * inv[i] % mod;
  53.     }
  54.  
  55.     for (int i = 2; i * i <= 2 * i + n; ++i) {
  56.         rec(i, i, i, 1, 1, 1);
  57.     }
  58.     ans[2] += 1;
  59.     for (int i = 2; i <= n; ++i) {
  60.         cout << ans[i] % mod << " ";
  61.     }
  62.     cout << "\n";
  63.  
  64.     return 0;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement