fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MOD = 1000000007LL;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int T;
  11.     if (!(cin >> T)) return 0;
  12.  
  13.     // Precompute C[n][k] cho n,k <= 62 là dư dả (n <= 60 bit)
  14.     const int MAXN = 65;
  15.     long long C[MAXN][MAXN];
  16.     for (int i = 0; i < MAXN; ++i) {
  17.         C[i][0] = C[i][i] = 1;
  18.         for (int j = 1; j < i; ++j) {
  19.             C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
  20.         }
  21.     }
  22.  
  23.     while (T--) {
  24.         unsigned long long n; 
  25.         cin >> n;
  26.  
  27.         if (n == 0) { // không xảy ra theo đề, nhưng cho chắc
  28.             cout << 1 << '\n';
  29.             continue;
  30.         }
  31.  
  32.         // tách bit của n
  33.         vector<int> a;
  34.         while (n > 0) {
  35.             a.push_back(n & 1ULL);
  36.             n >>= 1ULL;
  37.         }
  38.         int L = (int)a.size() - 1;
  39.  
  40.         // dp[carry] = số cách
  41.         // carry tối đa cỡ ~ L nên cấp mảng dư dả một chút
  42.         const int CARRY_MAX = 80;
  43.         vector<long long> dp(CARRY_MAX, 0), ndp(CARRY_MAX, 0);
  44.         dp[0] = 1;
  45.  
  46.         for (int t = 0; t <= L; ++t) {
  47.             fill(ndp.begin(), ndp.end(), 0);
  48.             for (int carry = 0; carry < CARRY_MAX; ++carry) if (dp[carry]) {
  49.                 for (int x = 0; x <= t + 1; ++x) { // chọn x biến bật ở đường chéo t
  50.                     if (((x + carry) & 1) == a[t]) {
  51.                         int carry2 = (x + carry) >> 1;
  52.                         if (carry2 < CARRY_MAX) {
  53.                             ndp[carry2] = (ndp[carry2] + dp[carry] * C[t+1][x]) % MOD;
  54.                         }
  55.                     }
  56.                 }
  57.             }
  58.             dp.swap(ndp);
  59.         }
  60.  
  61.         // sau cột cao nhất, không còn biến để chọn nên chỉ hợp lệ khi carry=0
  62.         cout << dp[0] % MOD << '\n';
  63.     }
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
5
8
10
stdout
copy 
4
10
14
https://ideone.com/b6swyN
language:
C++14 (gcc 8.3)
created:
22 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!