SHARE
TWEET

D_fft

a guest Apr 25th, 2013 1,076 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top