fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. using ll = long long;
  22.  
  23. const int mod=998244353;
  24.  
  25. template<typename T> inline void add(T &x, const T &y){
  26.     x+=y;
  27.     if(x>=mod) x-=mod;
  28.     if(x<0) x+=mod;
  29. }
  30.  
  31. inline int mask(int i){ return (1<<i); }
  32. inline bool bit(long long x ,long long i){ return (x>>i)&1; }
  33.  
  34. // so sánh bit-đôi với “ghi nhớ” trạng thái ở bit cao hơn
  35. inline int compare(long long b1, long long b2, long long cmp){
  36.     if(b1<b2) return 1;
  37.     if(b1>b2) return 0;
  38.     return cmp;
  39. }
  40.  
  41. long long n, k;
  42. int f[63][(1<<11)+3][13];
  43.  
  44. int main(){
  45.     ios::sync_with_stdio(false);
  46.     cin.tie(nullptr);
  47.  
  48.     cin>>n>>k;
  49.  
  50.     // chuyển strict-increasing (>=1) -> nondecreasing (>=0)
  51.     long long tri = k*(k+1)/2;        // 1+2+...+k
  52.     if(n < tri){ cout<<0; return 0; }
  53.     n -= tri;
  54.  
  55.     ms(f, 0); 
  56.     f[0][0][0]=1;
  57.  
  58.     // duyệt theo bit thấp -> cao để xử lý cộng với carry
  59.     ff(i, 0, 59) 
  60.         ff(cmp, 0, mask((int)k-1)-1) 
  61.             ff(carry, 0, (int)k-1) if(f[i][cmp][carry]){
  62.                 ff(nxt, 0, mask((int)k)-1){
  63.                     int ncmp=0;
  64.                     ff(j, 0, (int)k-2){
  65.                         if(compare(bit(nxt, j), bit(nxt, j+1), bit(cmp, j)))
  66.                             ncmp |= mask(j);
  67.                     }
  68.                     int tmp = carry + __builtin_popcount(nxt); // popcount cho int
  69.                     if(bit(n, i) != (tmp & 1)) cn;
  70.                     int ncarry = (tmp >> 1);                  // tối đa k-1
  71.                     add(f[i+1][ncmp][ncarry], f[i][cmp][carry]);
  72.                 }
  73.             }
  74.  
  75.     cout << f[60][mask((int)k-1)-1][0];
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 3.72s 10112KB
comments (?)
stdin 
485 9
stdout 
685437989
https://ideone.com/jlwrva
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!