welleyth

Problem C. DP (Optimized)

Sep 26th, 2021
956
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define pb push_back
  9. #define int long long
  10. #define uint __int128
  11. #define mp make_pair
  12. #define left left_compile
  13. #define right right_compile
  14.  
  15. #pragma GCC optimize("O3")
  16. #pragma GCC optimize("unroll-loops")
  17.  
  18. const int INF = (int)1e15;
  19. const int md = (int)998244353;
  20. const int MAXN = (int)1e18;
  21. const int N = (int)2e5 + 111;
  22. //const int L = 20;
  23. const int debug = 0;
  24. const long double eps = 1e-7;
  25.  
  26. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  27.  
  28. struct DSU{
  29.     int n;
  30.     vector<int> parent;
  31.     vector<int> sz;
  32.     vector<int> deep;
  33.     DSU(int nn){
  34.         n = nn;
  35.         parent.resize(n+1);
  36.         sz.resize(n+1,1);
  37.         deep.resize(n+1,1);
  38.         for(int i = 0; i <= n; i++)
  39.             parent[i] = i, sz[i] = 1, deep[i] = 1;
  40.     }
  41.     int find_parent(int x){
  42.         if(parent[x] == x)
  43.             return x;
  44.         return parent[x] = find_parent(parent[x]);
  45.     }
  46.     void union_sets(int a,int b){
  47.         a = find_parent(a);
  48.         b = find_parent(b);
  49.         if(a == b)
  50.             return;
  51.         if(deep[a] <= deep[b])
  52.             parent[a] = b, sz[b] += sz[a], deep[b] = max(deep[b],deep[a]+1);
  53.         else
  54.             parent[b] = a, sz[a] += sz[b], deep[a] = max(deep[a],deep[b]+1);
  55.     }
  56.     bool connected(int a,int b){
  57.         return find_parent(a) == find_parent(b);
  58.     }
  59. };
  60.  
  61. //typedef tree<
  62. //int,
  63. //null_type,
  64. //less_equal<int>,
  65. //rb_tree_tag,
  66. //tree_order_statistics_node_update>
  67. //ordered_set;
  68.  
  69. int bpow(int a,int b){
  70.     if(b <= 0)
  71.         return 1ll;
  72.     if(b % 2 == 0){
  73.         int t = bpow(a,b/2) % md;
  74.         return (t * t) % md;
  75.     }
  76.     return (a * bpow(a,b-1)) % md;
  77. }
  78.  
  79. int inv(int a){ /// return 1/a by PRIME modulo md
  80.     return bpow(a,md-2);
  81. }
  82.  
  83. //void myerase(ordered_set& st, int t){
  84. //    int r = st.order_of_key(t);
  85. //    ordered_set::iterator it = st.find_by_order(r);
  86. //    st.erase(it);
  87. //    return;
  88. //}
  89.  
  90. void init(){
  91.     return;
  92. }
  93.  
  94. void add(int& a,int b){
  95.     a = (a + b >= md ? a + b - md : a + b);
  96. }
  97.  
  98. //void sub(int& a,int b){
  99. //    a = (a < b ? a - b + md : a - b);
  100. //}
  101.  
  102. __int128 dp[1001];
  103.  
  104. void solve(){
  105.     int n;
  106.     cin >> n;
  107.  
  108.     dp[0] = 1;
  109.     for(int i = 1; i <= n; i += 2){
  110.         for(int j = 0; j <= n; j++){
  111.             if(j + i <= n)
  112.                 dp[j+i] += dp[j];
  113.         }
  114.     }
  115.  
  116.     string ans = "";
  117.     while(dp[n] > 0){
  118.         ans = (char)(dp[n] % 10 + '0') + ans;
  119.         dp[n] /= 10;
  120.     }
  121.  
  122.     cout << ans;
  123.  
  124.     return;
  125. }
  126. /// abcdefghijklmnopqrstuvwxyz
  127. /// x * sqrt(2) <= d
  128. /// k * x * sqrt(2) <= d
  129. /// x <= d / (sqrt(2) * k)
  130.  
  131. signed main(){
  132.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  133. //    freopen("input.txt","r",stdin);
  134. //    freopen("product.out","w",stdout);
  135.  
  136.     init();
  137.  
  138.     int tests = 1;
  139. //    cin >> tests;
  140.  
  141.     for(int _ = 1; _ <= tests; _++){
  142.         solve();
  143.     }
  144.  
  145. //    #ifdef __WIN32
  146. //        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  147. //    #endif
  148.  
  149.     return 0;
  150. }
  151. /***
  152.  
  153. bbabbabababbaaa
  154.  
  155. 9
  156. + passwords
  157. + paroli
  158. ? 1
  159. ? 2
  160. - 1
  161. ? 2
  162. + parol
  163. ? 2
  164. ? 3
  165.  
  166.  
  167. ***/
  168.  
RAW Paste Data