fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define file "o"
  5. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  6. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  7. #define nl "\n"
  8. #define ss " "
  9. #define pb emplace_back
  10. #define fi first
  11. #define se second
  12. #define sz(s) (int)s.size()
  13. #define all(s) (s).begin(), (s).end()
  14. #define ms(a,x) memset(a, x, sizeof (a))
  15. #define cn continue
  16. #define re exit(0)
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef vector<int> vi;
  22. typedef vector<ll> vll;
  23. typedef pair<int, int> pii;
  24. typedef pair<ll, ll> pll;
  25. typedef vector<pii> vpii;
  26. typedef vector<pll> vpll;
  27.  
  28. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  29. ll ran(ll l, ll r)
  30. {
  31.     return uniform_int_distribution<ll> (l, r)(rng);
  32. }
  33.  
  34. inline void rf()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(nullptr); cout.tie(nullptr);
  38.     if(fopen(file".inp","r"))
  39.     {
  40.         freopen(file".inp","r",stdin);
  41.         freopen(file".out","w",stdout);
  42.     }
  43. }
  44.  
  45. const int mod=998244353;
  46. const int maxn=2000+15;
  47. const ll inf=5e16;
  48.  
  49. template<typename T> inline void add(T &x, const T &y)
  50. {
  51.     x+=y;
  52.     if(x>=mod) x-=mod;
  53.     if(x<0) x+=mod;
  54. }
  55.  
  56. template<typename T> inline bool maxi(T &a, T b)
  57. {
  58.     if(a>=b) return 0;
  59.     a=b; return 1;
  60. }
  61.  
  62. template<typename T> inline bool mini(T &a, T b)
  63. {
  64.     if(a<=b) return 0;
  65.     a=b; return 1;
  66. }
  67.  
  68. inline int mask(int i)
  69. {
  70.     return (1<<i);
  71. }
  72.  
  73. inline bool bit(ll x ,int i)
  74. {
  75.     return (x>>i)&1;
  76. }
  77.  
  78. inline bool compare(bool b1, bool b2, bool cmp)
  79. {
  80.     if(b1<b2) return 1;
  81.     if(b1>b2) return 0;
  82.     return cmp;
  83. }
  84.  
  85. ll n; int k;
  86. int f[61][(1<<11)+1][12];
  87.  
  88. signed main()
  89. {
  90.     rf();
  91.     cin>>n>>k; n-=k;
  92.  
  93.     const int C  = mask(k-1);
  94.     const int N  = mask(k);
  95.     const int cmpAllOnes = C-1;
  96.     const unsigned mK1 = (k>=2 ? (unsigned)mask(k-1)-1u : 0u);
  97.  
  98.     static int pc[1<<11];
  99.     static int lt[1<<11];
  100.     static int eq[1<<11];
  101.     static vector<int> byParity[2];
  102.  
  103.     byParity[0].reserve(N/2+1); byParity[1].reserve(N/2+1);
  104.  
  105.     ff(x, 0, N-1){
  106.         pc[x] = __builtin_popcount((unsigned)x);
  107.         byParity[pc[x]&1].pb(x);
  108.         if (k>=2){
  109.             unsigned a = (unsigned)x;
  110.             unsigned b = a >> 1;
  111.             unsigned lt_mask = (~a) & b & mK1;
  112.             unsigned gt_mask = a & (~b) & mK1;
  113.             unsigned eq_mask = mK1 ^ (lt_mask | gt_mask);
  114.             lt[x] = (int)lt_mask;
  115.             eq[x] = (int)eq_mask;
  116.         }else{
  117.             lt[x] = 0; eq[x] = 0;
  118.         }
  119.     }
  120.  
  121.     f[0][0][0]=1;
  122.  
  123.     ff(i, 0, 59){
  124.         int bi = (int)bit(n, i);
  125.         ff(cmp, 0, C-1) ff(carry, 0, k-1) if(f[i][cmp][carry]){
  126.             int needParity = bi ^ (carry & 1);
  127.             const auto &cand = byParity[needParity];
  128.             for (int nxt : cand){
  129.                 int tmp = carry + pc[nxt];
  130.                 int ncarry = (tmp >> 1);
  131.                 int ncmp = (k>=2 ? ((cmp & eq[nxt]) | lt[nxt]) : 0);
  132.                 add(f[i+1][ncmp][ncarry], f[i][cmp][carry]);
  133.             }
  134.         }
  135.     }
  136.  
  137.     cout<<f[60][cmpAllOnes][0];
  138.     re;
  139. }
  140.  
Success #stdin #stdout 0.9s 5312KB
comments (?)
stdin 
487 10
stdout 
919633876
https://ideone.com/7nCNMt
language:
C++14 (gcc 8.3)
created:
2 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!