fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. const int MOD = 1'000'000'007;
  5.  
  6. // Thêm mod
  7. inline void addmod(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
  8. inline int64 mulmod(int64 a, int64 b) { return (a * b) % MOD; }
  9.  
  10. int main() {
  11. ios::sync_with_stdio(false);
  12. cin.tie(nullptr);
  13.  
  14.  
  15. long long n, x;
  16. int k;
  17. cin >> n >> k >> x;
  18.  
  19. // Tính phần cố định do x
  20. __int128 Sx128 = (__int128)x * k * (k + 1) / 2;
  21. if (Sx128 > n) {
  22.     cout << 0;
  23.     return 0;
  24. }
  25. long long remain = n - (long long)Sx128;
  26.  
  27. int fullSum = k * (k + 1) / 2;
  28.  
  29. // ways[s] = số subset của {1..k} có tổng s
  30. vector<int> ways(fullSum + 1);
  31. ways[0] = 1;
  32. for (int i = 1; i <= k; i++) {
  33.     for (int s = fullSum; s >= i; s--)
  34.         addmod(ways[s], ways[s - i]);
  35. }
  36.  
  37. vector<pair<int,int>> validS;
  38. for (int s = 0; s < fullSum; s++)
  39.     if (ways[s]) validS.emplace_back(s, ways[s]);
  40. int waysFull = ways[fullSum];
  41.  
  42. // dp[carry] = số cách tại bit hiện tại
  43. vector<int> dp(fullSum + 1), ndp(fullSum + 1);
  44. dp[0] = 1;
  45.  
  46. int maxBit = 0;
  47. while ((1LL << maxBit) <= (remain + (1LL << 11))) maxBit++;
  48. maxBit += 3;
  49.  
  50. for (int bit = 0; bit < maxBit; bit++) {
  51.     fill(ndp.begin(), ndp.end(), 0);
  52.     int bitN = (remain >> bit) & 1LL;
  53.     bool xbit = (x >> bit) & 1LL;
  54.  
  55.     for (int carry = 0; carry <= fullSum; carry++) if (dp[carry]) {
  56.         int cur = dp[carry];
  57.         if (xbit) {
  58.             int S = fullSum;
  59.             int parity = (carry + S) & 1;
  60.             if (parity != bitN) continue;
  61.             int nc = (carry + S) >> 1;
  62.             if (nc <= fullSum)
  63.                 ndp[nc] = (ndp[nc] + mulmod(cur, waysFull)) % MOD;
  64.         } else {
  65.             for (auto [S, w] : validS) {
  66.                 int parity = (carry + S) & 1;
  67.                 if (parity != bitN) continue;
  68.                 int nc = (carry + S) >> 1;
  69.                 if (nc <= fullSum)
  70.                     ndp[nc] = (ndp[nc] + mulmod(cur, w)) % MOD;
  71.             }
  72.         }
  73.     }
  74.     dp.swap(ndp);
  75. }
  76.  
  77. cout << dp[0] % MOD;
  78. return 0;
  79.  
  80.  
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
11 3 1
stdout 
Standard output is empty
https://ideone.com/VpPvnj
language:
C++14 (gcc 8.3)
created:
8 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!