fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. const int MOD = 1000000007;
  5.  
  6. int addmod(int a, int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
  7. int64 mulmod(int64 a, int64 b){ return (a*b)%MOD; }
  8.  
  9. int main(){
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     long long n, k, x;
  13.     if(!(cin >> n >> k >> x)) return 0;
  14.     long long T = k*(k+1)/2;
  15.     long long S = n - x * T;
  16.     if(S < 0){
  17.         cout << 0 << "\n";
  18.         return 0;
  19.     }
  20.     int Tmax = (int)T;
  21.  
  22.     // cnt[s] = số tập con của {1..k} có tổng s
  23.     vector<int> cnt(Tmax+1, 0);
  24.     cnt[0] = 1;
  25.     for(int i=1;i<=k;i++){
  26.         for(int s=Tmax; s>=i; --s){
  27.             cnt[s] = addmod(cnt[s], cnt[s - i]);
  28.         }
  29.     }
  30.  
  31.     // Precompute list of values v with cnt[v] != 0 to skip zeros
  32.     vector<int> vals;
  33.     vals.reserve(Tmax+1);
  34.     for(int v=0; v<=Tmax; ++v) if(cnt[v]) vals.push_back(v);
  35.  
  36.     // Determine maximum pos to process:
  37.     int maxSbit = 0;
  38.     if(S > 0) maxSbit = 63 - __builtin_clzll(S); // highest bit index of S
  39.     int LOGT = 0;
  40.     while((1LL<<LOGT) <= Tmax) ++LOGT;
  41.     int MAXPOS = maxSbit + LOGT + 3; // safe margin
  42.  
  43.     // dp[tight][carry] : tight=0/1
  44.     // carry ranges 0..Tmax
  45.     vector<int> dp_tight0(Tmax+1, 0), dp_tight1(Tmax+1, 0);
  46.     dp_tight1[0] = 1;
  47.  
  48.     for(int pos=0; pos<=MAXPOS; ++pos){
  49.         vector<int> ndp0(Tmax+1, 0), ndp1(Tmax+1, 0);
  50.         int Sbit = ( (S>>pos) & 1 );
  51.         bool xbit = ((x>>pos) & 1);
  52.         // list of possible v for this pos
  53.         if(xbit){
  54.             // must choose v = 0
  55.             int v = 0;
  56.             int ways = cnt[v];
  57.             // handle tight=0
  58.             for(int c=0;c<=Tmax;++c){
  59.                 int cur = dp_tight0[c];
  60.                 if(!cur) continue;
  61.                 int sum = c + v;
  62.                 int bit = sum & 1;
  63.                 int nc = sum >> 1;
  64.                 // tight=0 stays 0
  65.                 ndp0[nc] = (ndp0[nc] + (int64)cur * ways) % MOD;
  66.             }
  67.             // handle tight=1
  68.             for(int c=0;c<=Tmax;++c){
  69.                 int cur = dp_tight1[c];
  70.                 if(!cur) continue;
  71.                 int sum = c + v;
  72.                 int bit = sum & 1;
  73.                 if(bit > Sbit) continue;
  74.                 int nc = sum >> 1;
  75.                 int ntight = (bit == Sbit) ? 1 : 0;
  76.                 if(ntight) ndp1[nc] = (ndp1[nc] + (int64)cur * ways) % MOD;
  77.                 else ndp0[nc] = (ndp0[nc] + (int64)cur * ways) % MOD;
  78.             }
  79.         }else{
  80.             // xbit == 0 => v can be 0..Tmax with multiplicity cnt[v]
  81.             // iterate possible v where cnt[v]>0
  82.             for(int v : vals){
  83.                 int ways = cnt[v];
  84.                 // tight=0 transitions
  85.                 for(int c=0;c<=Tmax;++c){
  86.                     int cur = dp_tight0[c];
  87.                     if(!cur) continue;
  88.                     int sum = c + v;
  89.                     int nc = sum >> 1;
  90.                     ndp0[nc] = (ndp0[nc] + (int64)cur * ways) % MOD;
  91.                 }
  92.                 // tight=1 transitions
  93.                 for(int c=0;c<=Tmax;++c){
  94.                     int cur = dp_tight1[c];
  95.                     if(!cur) continue;
  96.                     int sum = c + v;
  97.                     int bit = sum & 1;
  98.                     if(bit > Sbit) continue;
  99.                     int nc = sum >> 1;
  100.                     int ntight = (bit == Sbit) ? 1 : 0;
  101.                     if(ntight) ndp1[nc] = (ndp1[nc] + (int64)cur * ways) % MOD;
  102.                     else ndp0[nc] = (ndp0[nc] + (int64)cur * ways) % MOD;
  103.                 }
  104.             }
  105.         }
  106.         dp_tight0.swap(ndp0);
  107.         dp_tight1.swap(ndp1);
  108.     }
  109.  
  110.     // After processing all bits, valid only if carry == 0
  111.     int ans = dp_tight0[0];
  112.     ans = addmod(ans, dp_tight1[0]);
  113.     cout << ans << "\n";
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
11 3 1
stdout 
479794
https://ideone.com/R67BdQ
language:
C++14 (gcc 8.3)
created:
9 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!