Guest User

D_fft

a guest
Apr 25th, 2013
1,516
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cctype>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <complex>
  10. #include <deque>
  11. #include <functional>
  12. #include <fstream>
  13. #include <iostream>
  14. #include <map>
  15. #include <memory.h>
  16. #include <numeric>
  17. #include <queue>
  18. #include <set>
  19. #include <stack>
  20. #include <string>
  21. #include <sstream>
  22. #include <vector>
  23. #include <utility>
  24. #include <cmath>
  25. using namespace std;
  26.  
  27. #define pb push_back
  28. #define mp make_pair
  29. #define sz(a) (int)(a).size()
  30. #define all(a) (a).begin(), (a).end()
  31.  
  32. #define forn(i,n) for (int i=0; i<int(n); ++i)
  33. #define fornd(i,n) for (int i=int(n)-1; i>=0; --i)
  34. #define xrange(i,a,b) for (int i=int(a); i<int(b); ++i)
  35.  
  36. typedef long long ll;
  37. typedef long double ld;
  38. typedef unsigned long long ull;
  39.  
  40.  
  41. const int INF = (int) 1e9;
  42. const long long INF64 = (long long) 1e18;
  43. const long double eps = 1e-9;
  44. const long double pi = 3.14159265358979323846;
  45.  
  46. const int mod = 7340033;
  47. const ll root = 5;
  48. const ll root_1 = 4404020;
  49. const ll root_pw = 1<<20;
  50.  
  51. int rev_element[7340033];
  52.  
  53. ll getmod(ll a, ll tmod){
  54.     return ((a%tmod)+tmod)%tmod;
  55. }
  56.  
  57. void fft (vector<ll> & a, bool invert) {
  58.     int n = (int) a.size();
  59.  
  60.     for (int i=1, j=0; i<n; ++i) {
  61.         int bit = n >> 1;
  62.         for (; j>=bit; bit>>=1)
  63.             j -= bit;
  64.         j += bit;
  65.         if (i < j)
  66.             swap (a[i], a[j]);
  67.     }
  68.  
  69.     for (int len=2; len<=n; len<<=1) {
  70.         ll wlen = invert ? root_1 : root;
  71.         for (int i=len; i<root_pw; i<<=1)
  72.             wlen = ll (wlen * 1ll * wlen % mod);
  73.         for (int i=0; i<n; i+=len) {
  74.             ll w = 1;
  75.             for (int j=0; j<len/2; ++j) {
  76.                 ll u = a[i+j],  v = ll (a[i+j+len/2] * 1ll * w % mod);
  77.                 a[i+j] = getmod(u+v,mod);
  78.                 a[i+j+len/2] = getmod(u-v,mod);
  79.                 w = ll (w * 1ll * wlen % mod);
  80.             }
  81.         }
  82.     }
  83.     if (invert) {
  84.         ll nrev = rev_element[n];
  85.         for (int i=0; i<n; ++i)
  86.             a[i] = int (a[i] * 1ll * nrev % mod);
  87.     }
  88. }
  89.  
  90. void precalc(){
  91.     rev_element[1] = 1;
  92.     for (int i=2; i<mod; i++)
  93.         rev_element[i] = (mod - (mod/i) * rev_element[mod%i] % mod) % mod;
  94. }
  95.  
  96.  
  97. void multiply (const vector<ll> & a, const vector<ll> & b, vector<ll> & res) {
  98.     vector <ll> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
  99.     size_t n = 1;
  100.     while (n < max (a.size(), b.size()))  n <<= 1;
  101.     n <<= 1;
  102.     fa.resize (n),  fb.resize (n);
  103.     fft (fa, false),  fft (fb, false);
  104.     forn(i,n)
  105.         fa[i] *= fb[i];
  106.     fft (fa, true);
  107.     res.resize (n);
  108.     forn(i,n)
  109.         res[i] = fa[i] % mod;
  110. }
  111.  
  112. int MN = 29;
  113. int MK = 1001;
  114. vector <vector <ll> > dp(MN+2,vector <ll> (MK,0));
  115. vector <ll> d;
  116.  
  117. void init(){
  118.     int m;
  119.     for (int i=0; i<=MN; i++){
  120.         dp[i][0] = 1;
  121.         multiply(dp[i],dp[i],d);
  122.         d.resize(MK);
  123.         multiply(d,d,dp[i+1]);
  124.         dp[i+1].insert(dp[i+1].begin(),0);
  125.         dp[i+1].resize(MK);
  126.     }
  127. }
  128.  
  129. int main(){
  130. #ifdef dudkamaster
  131.     freopen("input.txt","rt",stdin);
  132.     freopen("output.txt","wt",stdout);
  133. #endif
  134.     precalc();
  135.     init();
  136.     int tc;
  137.     scanf("%d", &tc);
  138.     forn(i,tc){
  139.         ll n,k;
  140.         cin >> n >> k;
  141.         int iter = 0;
  142.         while (n>1 && n&1)
  143.             iter++, n>>=1;
  144.         cout << dp[iter][k] << endl;
  145.     }
  146.     return 0;
  147. }
RAW Paste Data