fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define file "diduduadi"
  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.  
  102.     ff(x, 0, N-1){
  103.         pc[x] = __builtin_popcount((unsigned)x);
  104.         if (k>=2){
  105.             unsigned a = (unsigned)x;
  106.             unsigned b = a >> 1;
  107.             unsigned lt_mask = (~a) & b & mK1;
  108.             unsigned gt_mask = a & (~b) & mK1;
  109.             unsigned eq_mask = mK1 ^ (lt_mask | gt_mask);
  110.             lt[x] = (int)lt_mask;
  111.             eq[x] = (int)eq_mask;
  112.         }else{
  113.             lt[x] = 0; eq[x] = 0;
  114.         }
  115.     }
  116.  
  117.     vector<vector<vector<uint16_t>>> trans_idx(C, vector<vector<uint16_t>>(k+1));
  118.     vector<vector<vector<uint16_t>>> trans_cnt(C, vector<vector<uint16_t>>(k+1));
  119.     vector<int> cnt((k+1)*C);
  120.  
  121.     ff(cmp,0,C-1){
  122.         fill(all(cnt),0);
  123.         ff(x,0,N-1){
  124.             int t = pc[x];
  125.             int ncmp = (k>=2 ? ((cmp & eq[x]) | lt[x]) : 0);
  126.             cnt[t*C + ncmp]++;
  127.         }
  128.         ff(t,0,k){
  129.             auto &vi = trans_idx[cmp][t];
  130.             auto &vc = trans_cnt[cmp][t];
  131.             vi.reserve(C/2+1);
  132.             vc.reserve(C/2+1);
  133.             ff(ncmp,0,C-1){
  134.                 int c = cnt[t*C + ncmp];
  135.                 if(c){
  136.                     vi.push_back((uint16_t)ncmp);
  137.                     vc.push_back((uint16_t)c);
  138.                 }
  139.             }
  140.         }
  141.     }
  142.  
  143.     f[0][0][0]=1;
  144.  
  145.     ff(i, 0, 59){
  146.         int bi = (int)bit(n, i);
  147.         ff(cmp, 0, C-1) ff(carry, 0, k-1) if(f[i][cmp][carry]){
  148.             int needParity = bi ^ (carry & 1);
  149.             for (int t = needParity; t <= k; t += 2){
  150.                 int ncarry = (carry + t) >> 1;
  151.                 const auto &vi = trans_idx[cmp][t];
  152.                 const auto &vc = trans_cnt[cmp][t];
  153.                 int L = (int)vi.size();
  154.                 int base = f[i][cmp][carry];
  155.                 for (int j = 0; j < L; ++j){
  156.                     int ncmp = vi[j];
  157.                     int c = vc[j];
  158.                     int mul = (int)((1LL * base * c) % mod);
  159.                     add(f[i+1][ncmp][ncarry], mul);
  160.                 }
  161.             }
  162.         }
  163.     }
  164.  
  165.     cout<<f[60][cmpAllOnes][0];
  166.     re;
  167. }
  168.  
Success #stdin #stdout 0.52s 11464KB
comments (?)
stdin 
487 10
stdout 
919633876
https://ideone.com/3qAs5V
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!