Advertisement
welleyth

A. Good Arrays

Apr 13th, 2022
991
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. //#define int long long
  7. #define pb push_back
  8. #define mp make_pair
  9.  
  10. #pragma GCC optimize("Ofast")
  11. #pragma GCC optimize("unroll-loops")
  12. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
  13. #pragma GCC target("avx,avx2")
  14.  
  15. constexpr int INF = (int)1e9;
  16. constexpr int N = (int)5e7 + 111;
  17. constexpr int MAXN = (int)1e5 + 11;
  18. constexpr int md = (int)998244353;
  19.  
  20. mt19937_64 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
  21.  
  22. template<class T>
  23. using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
  24. template<class T>
  25. using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  26.  
  27. int bpow(int a,int b){
  28.     if(b == 0)
  29.         return 1;
  30.     if(b % 2 == 0){
  31.         int t = bpow(a,b>>1);
  32.         return (1ll * t * t) % md;
  33.     }
  34.     return (1ll * a * bpow(a,b-1)) % md;
  35. }
  36.  
  37. int inv(int a){
  38.     return bpow(a,md-2);
  39. }
  40.  
  41. int fac[N];
  42.  
  43. int C(int n,int k){
  44.     if(k > n)
  45.         return 0;
  46.     return (((1ll * fac[n] * inv(fac[k])) % md) * inv(fac[n-k])) % md;
  47. }
  48. void add(int& a,int b){
  49.     a += b; if(a >= md) a -= md;
  50. }
  51.  
  52. int f[N];
  53. int mn[N];
  54. vector<int> pr;
  55.  
  56. void solve(){
  57.     int n,c;
  58.     cin >> n >> c;
  59.  
  60.     fac[0] = 1;
  61.  
  62.     for(int i = 1; i < N; i++){
  63.         fac[i] = (1ll * fac[i-1] * i) % md;
  64.     }
  65.  
  66.     for(int i = 2; i < N; i++){
  67.         if(mn[i] == 0){
  68.             mn[i] = i;
  69.             pr.pb(i);
  70.         }
  71.         for(int j = 0; j < pr.size() && pr[j] <= mn[i] && i*pr[j] < N; j++)
  72.             mn[i*pr[j]] = pr[j];
  73.     }
  74.  
  75. //    return;
  76.     int ans = 1;
  77.     f[1] = 1;
  78.  
  79.     int precalc[33];
  80.     for(int x = 1; x < 33; x++){
  81.         precalc[x] = C(n-1+x,x);
  82.     }
  83.  
  84.     int P[33];
  85.     int ptr;
  86.     for(int i = 2; i <= c; i++){
  87.         int cnt = 0;
  88.         int t = i;
  89.         int p = mn[i];
  90.         while(t > 1 && t % p == 0){
  91.             t /= p;
  92.             cnt++;
  93.         }
  94.         if(t == 1){
  95.             f[i] = precalc[cnt];
  96.             add(ans,f[i]);
  97.             continue;
  98.         }
  99.         f[i] = (1ll * f[t] * f[i/t]) % md;
  100.         add(ans,f[i]);
  101. //        cerr << i << " " << f[i] << "\n";
  102.     }
  103.  
  104.     cout << ans%md;
  105.  
  106.     return;
  107. }
  108. signed main(){
  109.     ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  110.     int tests = 1;
  111. //    cin >> tests;
  112.     while(tests--){
  113.         solve();
  114.     }
  115. }
  116. /**
  117.  
  118. ooo
  119.  
  120. p^2
  121.  
  122. 4
  123. 4 4 4
  124. 2 4 4
  125. 2 2 4
  126. 1 4 4
  127. 1 1 4
  128. 1 2 4
  129.  
  130. C(n-1+d,d) = C(4,2) = 4!/2!2! = 24/4 = 6
  131.  
  132. C(n-1+d,d)
  133.  
  134. **/
  135.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement