welleyth

Problem C. DP

Sep 26th, 2021
916
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][1001];
  103.  
  104. void solve(){
  105.     int n;
  106.     cin >> n;
  107.  
  108.     for(int i = 0; i <= n; i++)
  109.         dp[0][i] = 1;
  110.  
  111.     for(int i = 1; i <= n; i++){
  112.         for(int j = 1; j <= n; j++){
  113.             dp[i][j] = dp[i][j-1];
  114.             if(i - j >= 0 && j % 2 == 1)
  115.                 dp[i][j] += dp[i-j][j];
  116.         }
  117.     }
  118.  
  119.     string ans = "";
  120.     while(dp[n][n] > 0){
  121.         ans = (char)(dp[n][n] % 10 + '0') + ans;
  122.         dp[n][n] /= 10;
  123.     }
  124.  
  125.     cout << ans;
  126.  
  127.     return;
  128. }
  129. /// abcdefghijklmnopqrstuvwxyz
  130. /// x * sqrt(2) <= d
  131. /// k * x * sqrt(2) <= d
  132. /// x <= d / (sqrt(2) * k)
  133.  
  134. signed main(){
  135.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  136. //    freopen("input.txt","r",stdin);
  137. //    freopen("product.out","w",stdout);
  138.  
  139.     init();
  140.  
  141.     int tests = 1;
  142. //    cin >> tests;
  143.  
  144.     for(int _ = 1; _ <= tests; _++){
  145.         solve();
  146.     }
  147.  
  148. //    #ifdef __WIN32
  149. //        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  150. //    #endif
  151.  
  152.     return 0;
  153. }
  154. /***
  155.  
  156. bbabbabababbaaa
  157.  
  158. 9
  159. + passwords
  160. + paroli
  161. ? 1
  162. ? 2
  163. - 1
  164. ? 2
  165. + parol
  166. ? 2
  167. ? 3
  168.  
  169.  
  170. ***/
  171.  
RAW Paste Data