fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int MOD = 998244353;  // Changed to standard CP modulo
  5.  
  6. void solve() {
  7.     int n;
  8.     cin >> n;
  9.     vector<int> a(n);
  10.     for(int i = 0; i < n; i++) {
  11.         cin >> a[i];
  12.     }
  13.  
  14.     vector<int> dp(4000007, 0);
  15.     dp[0] = 1;
  16.     vector<int> hold(23);
  17.     hold[0] = hold[1] = 0;
  18.  
  19.     // Precompute hold array
  20.     for(int i = 2; i < 23; i++) {
  21.         hold[i] = hold[i-1] * 2 + (1LL << i);
  22.     }
  23.  
  24.     // DP computation
  25.     for(int i = 1; i <= 4e6+5; i++) {
  26.         for(int j = 0; j < 23; j++) {
  27.             if(i >= hold[j]) {  // More efficient bounds check
  28.                 dp[i] = (dp[i] + dp[i-hold[j]]) % MOD;  // Inline modulo
  29.             }
  30.         }
  31.     }
  32.  
  33.     // Output results
  34.     for(int x : a) {
  35.         cout << dp[x] << '\n';  // Using '\n' instead of endl for faster output
  36.     }
  37. }
  38.  
  39. int32_t main() {
  40.     ios_base::sync_with_stdio(false);  // Fast I/O
  41.     cin.tie(NULL);
  42.  
  43.     int t = 1;
  44.     //cin >> t;
  45.     while(t--) {
  46.         solve();
  47.     }
  48.     return 0;
  49. }
Success #stdin #stdout 0.31s 34312KB
comments (?)
stdin
copy 
4
2 4 8 32
stdout
copy 
0
1
1
7
https://ideone.com/WdZqcQ
language:
C++ (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!