fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. const int64 MOD = 1000000007LL;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     long long n;
  10.     int k;
  11.     long long x;
  12.     if(!(cin >> n >> k >> x)) return 0;
  13.  
  14.     // Sum of indices
  15.     int T = k * (k + 1) / 2;
  16.  
  17.     // cnt[s] = number of subsets of {1..k} with sum s (mod MOD)
  18.     vector<int64> cnt(T + 1, 0);
  19.     cnt[0] = 1;
  20.     for(int i = 1; i <= k; ++i){
  21.         for(int s = T; s >= i; --s){
  22.             cnt[s] += cnt[s - i];
  23.             if(cnt[s] >= MOD) cnt[s] -= MOD;
  24.         }
  25.     }
  26.  
  27.     // Build options for x_b == 0: pairs (S, multiplicity)
  28.     vector<pair<int,int64>> opts_zero;
  29.     opts_zero.reserve(T + 1);
  30.     for(int s = 0; s <= T; ++s){
  31.         int64 m = cnt[s];
  32.         if(s == T){
  33.             m = (m - 1) % MOD; // exclude the "all-ones" vector
  34.             if(m < 0) m += MOD;
  35.         }
  36.         if(m != 0) opts_zero.emplace_back(s, m);
  37.     }
  38.     // option for x_b == 1: only S = T with multiplicity 1
  39.     pair<int,int64> opt_one = {T, 1};
  40.  
  41.     // Determine number of bits B to process
  42.     // bits(n) + enough extra bits to carry all S-values (max S ~ T requires ~log2(T) extra bits)
  43.     int bits_n = (n == 0 ? 1 : 64 - __builtin_clzll((unsigned long long)n));
  44.     int extra = 0;
  45.     while((1LL << extra) <= T) ++extra; // need ceil(log2(T+1))
  46.     int B = bits_n + extra + 2; // +2 safety
  47.     if(B < 1) B = 1;
  48.     if(B > 200) B = 200; // safety cap
  49.  
  50.     // get bits arrays for n and x
  51.     vector<int> nb(B, 0), xb(B, 0);
  52.     {
  53.         long long tmp = n;
  54.         for(int i = 0; i < B; ++i){
  55.             nb[i] = (tmp & 1LL) ? 1 : 0;
  56.             tmp >>= 1;
  57.         }
  58.     }
  59.     {
  60.         long long tmp = x;
  61.         for(int i = 0; i < B; ++i){
  62.             xb[i] = (tmp & 1LL) ? 1 : 0;
  63.             tmp >>= 1;
  64.         }
  65.     }
  66.  
  67.     // DP arrays: two layers for current bit: curr_tight0[c], curr_tight1[c] where c=carry (0..T)
  68.     vector<int64> curr0(T+1, 0), curr1(T+1, 0);
  69.     vector<int64> next0(T+1, 0), next1(T+1, 0);
  70.     curr1[0] = 1; // at bit 0, carry 0, tight = 1 (so far equal to n)
  71.  
  72.     for(int b = 0; b < B; ++b){
  73.         fill(next0.begin(), next0.end(), 0);
  74.         fill(next1.begin(), next1.end(), 0);
  75.  
  76.         // choose options based on xb[b]
  77.         const vector<pair<int,int64>> *opts_ptr = nullptr;
  78.         vector<pair<int,int64>> single_opt;
  79.         if(xb[b] == 0){
  80.             opts_ptr = &opts_zero;
  81.         } else {
  82.             single_opt.clear();
  83.             single_opt.push_back(opt_one);
  84.             opts_ptr = &single_opt;
  85.         }
  86.         const auto &opts = *opts_ptr;
  87.  
  88.         // transitions from tight == 0 (already < n), no restriction on bit
  89.         for(int carry = 0; carry <= T; ++carry){
  90.             int64 ways = curr0[carry];
  91.             if(ways == 0) continue;
  92.             for(const auto &pr : opts){
  93.                 int S = pr.first;
  94.                 int64 mult = pr.second;
  95.                 int total = carry + S;
  96.                 int bit = total & 1;
  97.                 int carry2 = total >> 1;
  98.                 if(carry2 > T) continue; // safety, shouldn't happen
  99.                 int64 add = ( (__int128)ways * mult ) % MOD;
  100.                 next0[carry2] += add;
  101.                 if(next0[carry2] >= MOD) next0[carry2] -= MOD;
  102.             }
  103.         }
  104.  
  105.         // transitions from tight == 1 (must obey nb[b])
  106.         for(int carry = 0; carry <= T; ++carry){
  107.             int64 ways = curr1[carry];
  108.             if(ways == 0) continue;
  109.             for(const auto &pr : opts){
  110.                 int S = pr.first;
  111.                 int64 mult = pr.second;
  112.                 int total = carry + S;
  113.                 int bit = total & 1;
  114.                 if(bit > nb[b]) continue; // would exceed n at this bit
  115.                 int carry2 = total >> 1;
  116.                 if(carry2 > T) continue; // safety
  117.                 int next_tight = (bit == nb[b]) ? 1 : 0;
  118.                 int64 add = ( (__int128)ways * mult ) % MOD;
  119.                 if(next_tight){
  120.                     next1[carry2] += add;
  121.                     if(next1[carry2] >= MOD) next1[carry2] -= MOD;
  122.                 } else {
  123.                     next0[carry2] += add;
  124.                     if(next0[carry2] >= MOD) next0[carry2] -= MOD;
  125.                 }
  126.             }
  127.         }
  128.  
  129.         curr0.swap(next0);
  130.         curr1.swap(next1);
  131.     }
  132.  
  133.     // After processing B bits, accept states where carry == 0 (no leftover) and tight can be 0 or 1
  134.     int64 ans = (curr0[0] + curr1[0]) % MOD;
  135.     cout << ans << "\n";
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
11 3 1
stdout 
267731
https://ideone.com/Dlk4vf
language:
C++14 (gcc 8.3)
created:
3 days 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!