API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Aug 26th, 2022
794
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.78 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define pf push_front
  17. #define mp make_pair
  18. #define ins insert
  19. #define btpc __builtin_popcount
  20. #define btclz __builtin_clz
  21.  
  22. #define sz(x) (int)(x.size());
  23. #define all(x) x.begin(), x.end()
  24. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  25.  
  26. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  27.  
  28. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  29. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  30. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  31.  
  32. template<class X, class Y>
  33.     bool minimize(X &x, const Y &y) {
  34.         if (x > y)
  35.         {
  36.             x = y;
  37.             return true;
  38.         }
  39.         return false;
  40.     }
  41. template<class X, class Y>
  42.     bool maximize(X &x, const Y &y) {
  43.         if (x < y)
  44.         {
  45.             x = y;
  46.             return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51. const int MOD = 1e9 + 7; //998244353
  52.  
  53. template<class X, class Y>
  54.     void add(X &x, const Y &y) {
  55.         x = (x + y);
  56.         if(x >= MOD) x -= MOD;
  57.     }
  58.  
  59. template<class X, class Y>
  60.     void sub(X &x, const Y &y) {
  61.         x = (x - y);
  62.         if(x < 0) x += MOD;
  63.     }
  64.  
  65. /* Author : Le Ngoc Bao Anh, 11A5, LQD High School for Gifted Student*/
  66.  
  67. const ll INF = 1e9;
  68. const int N = 1e5 + 10;
  69.  
  70. #define double long double
  71. namespace FFT {
  72.     const int maxf = 1 << 20;
  73.     struct cp {
  74.         double x, y;
  75.         cp(double x = 0, double y = 0) : x(x), y(y) {}
  76.         cp operator + (const cp& rhs) const {
  77.             return cp(x + rhs.x, y + rhs.y);
  78.         }
  79.         cp operator - (const cp& rhs) const {
  80.             return cp(x - rhs.x, y - rhs.y);
  81.         }
  82.         cp operator * (const cp& rhs) const {
  83.             return cp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  84.         }
  85.         cp operator !() const {
  86.             return cp(x, -y);
  87.         }
  88.     } rts[maxf + 1];
  89.     cp fa[maxf], fb[maxf];
  90.     cp fc[maxf], fd[maxf];
  91.  
  92.     int bitrev[maxf];
  93.     void fftinit() {
  94.         int k = 0; while ((1 << k) < maxf) k++;
  95.         bitrev[0] = 0;
  96.         for (int i = 1; i < maxf; i++) {
  97.             bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
  98.         }
  99.         double PI = acos((double) -1.0);
  100.         rts[0] = rts[maxf] = cp(1, 0);
  101.         for (int i = 1; i + i <= maxf; i++) {
  102.             rts[i] = cp(cos(i * 2 * PI / maxf), sin(i * 2 * PI / maxf));
  103.         }
  104.         for (int i = maxf / 2 + 1; i < maxf; i++) {
  105.             rts[i] = !rts[maxf - i];
  106.         }
  107.     }
  108.     void dft(cp a[], int n, int sign) {
  109.         static int isinit;
  110.         if (!isinit) {
  111.             isinit = 1;
  112.             fftinit();
  113.         }
  114.         int d = 0; while ((1 << d) * n != maxf) d++;
  115.         for (int i = 0; i < n; i++) {
  116.             if (i < (bitrev[i] >> d)) {
  117.                 swap(a[i], a[bitrev[i] >> d]);
  118.             }
  119.         }
  120.         for (int len = 2; len <= n; len <<= 1) {
  121.             int delta = maxf / len * sign;
  122.             for (int i = 0; i < n; i += len) {
  123.                 cp *x = a + i,*y = a + i + (len >> 1), *w = sign > 0 ? rts : rts + maxf;
  124.                 for (int k = 0; k + k < len; k++) {
  125.                     cp z = *y * *w;
  126.                     *y = *x - z, *x = *x + z;
  127.                     x++, y++, w += delta;
  128.                 }
  129.             }
  130.         }
  131.         if (sign < 0) {
  132.             for (int i = 0; i < n; i++) {
  133.                 a[i].x /= n;
  134.                 a[i].y /= n;
  135.             }
  136.         }
  137.     }
  138.     void multiply(int a[], int b[], int na, int nb, long long c[], int dup = 0) {
  139.         int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
  140.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  141.         for (int i = 0; i < na; i++) fa[i] = cp(a[i]);
  142.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i]);
  143.         dft(fa, n, 1);
  144.         if (dup) {
  145.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  146.         }
  147.         else {
  148.             dft(fb, n, 1);
  149.         }
  150.         for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i];
  151.         dft(fa, n, -1);
  152.         for (int i = 0; i < n; i++) c[i] = (long long) floor(fa[i].x + 0.5);
  153.     }
  154.     void multiply(int a[], int b[], int na, int nb, int c[], int mod = (int) 1e9 + 7, int dup = 0) {
  155.         int n = na + nb - 1;
  156.         while (n != (n & -n)) n += n & -n;
  157.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  158.         static const int magic = 15;
  159.         for (int i = 0; i < na; i++) fa[i] = cp(a[i] >> magic, a[i] & (1 << magic) - 1);
  160.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i] >> magic, b[i] & (1 << magic) - 1);
  161.         dft(fa, n, 1);
  162.         if (dup) {
  163.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  164.         }
  165.         else {
  166.             dft(fb, n, 1);
  167.         }
  168.         for (int i = 0; i < n; i++) {
  169.             int j = (n - i) % n;
  170.             cp x = fa[i] + !fa[j];
  171.             cp y = fb[i] + !fb[j];
  172.             cp z = !fa[j] - fa[i];
  173.             cp t = !fb[j] - fb[i];
  174.             fc[i] = (x * t + y * z) * cp(0, 0.25);
  175.             fd[i] = x * y * cp(0, 0.25) + z * t * cp(-0.25, 0);
  176.         }
  177.         dft(fc, n, -1), dft(fd, n, -1);
  178.         for (int i = 0; i < n; i++) {
  179.             long long u = ((long long) floor(fc[i].x + 0.5)) % mod;
  180.             long long v = ((long long) floor(fd[i].x + 0.5)) % mod;
  181.             long long w = ((long long) floor(fd[i].y + 0.5)) % mod;
  182.             c[i] = ((u << magic) + v + (w << magic + magic)) % mod;
  183.         }
  184.     }
  185.     vector<int> multiply(vector<int> a, vector<int> b, int mod = (int) 1e9 + 7) {
  186.         static int fa[maxf], fb[maxf], fc[maxf];
  187.         int na = a.size(), nb = b.size();
  188.         for (int i = 0; i < na; i++) fa[i] = a[i];
  189.         for (int i = 0; i < nb; i++) fb[i] = b[i];
  190.         multiply(fa, fb, na, nb, fc, mod, a == b);
  191.         int k = na + nb - 1;
  192.         vector<int> res(k);
  193.         for (int i = 0; i < k; i++) res[i] = fc[i];
  194.         return res;
  195.     }
  196.     int fpow(int a, int k, int p) {
  197.         if (!k) return 1;
  198.         int res = a, t = a; k--;
  199.         while (k) {
  200.             if (k & 1) res = (long long) res * t % p;
  201.             t = (long long) t * t % p;
  202.             k >>= 1;
  203.         }
  204.         return res;
  205.     }
  206.     vector<int> invert(vector<int> a, int n, int mod){
  207.         assert(a[0] != 0);
  208.         vector<int> x(1, fpow(a[0], mod - 2, mod));
  209.         while (x.size() < n) {
  210.             vector<int> tmp(a.begin(), a.begin() + min(a.size(), 2 * x.size()));
  211.             vector<int> nx = multiply(multiply(x, x, mod), tmp, mod);
  212.             x.resize(2 * x.size());
  213.             for (int i = 0; i < x.size(); i++) {
  214.                 x[i] += x[i];
  215.                 x[i] -= nx[i];
  216.                 if (x[i] < 0) x[i] += mod;
  217.                 if (x[i] >= mod) x[i] -= mod;
  218.             }
  219.         }
  220.         x.resize(n);
  221.         return x;
  222.     }
  223.     pair<vector<int>, vector<int> > divmod(vector<int> a, vector<int> b, int mod) {
  224.         int n = a.size(), m = b.size();
  225.         if (n < m) {
  226.             return make_pair(vector<int>(), a);
  227.         }
  228.         reverse(a.begin(), a.end());
  229.         reverse(b.begin(), b.end());
  230.         vector<int> rb = invert(b, n - m + 1, mod);
  231.         vector<int> d = multiply(a, rb, mod);
  232.         reverse(a.begin(), a.end());
  233.         reverse(b.begin(), b.end());
  234.         while (d.size() > n - m + 1) d.pop_back();
  235.         reverse(d.begin(), d.end());
  236.         vector<int> r = multiply(d, b, mod);
  237.         while (r.size() >= m) r.pop_back();
  238.         for (int i = 0; i < m; i++) {
  239.             r[i] = a[i] - r[i];
  240.             if (r[i] < 0) r[i] += mod;
  241.         }
  242.         return make_pair(d, r);
  243.     }
  244.     vector<int> chirpz_transform(vector<int> a, int z, int k, int mod) {
  245.         int n = a.size();
  246.         vector<int> x;
  247.         vector<int> y;
  248.         int iz = fpow(z, mod - 2, mod);
  249.         for (int i = 0; i < n; i++) {
  250.             x.push_back((long long) a[i] * fpow(z, (long long) i * i, mod) % mod);
  251.         }
  252.         for (int i = 1 - n; i < k; i++) {
  253.             y.push_back(fpow(iz, (long long) i * i, mod));
  254.         }
  255.         vector<int> r = FFT::multiply(x, y, mod);
  256.         vector<int> res(k);
  257.         for (int i = 0; i < k; i++) {
  258.             res[i] = (long long) r[i + n - 1] * fpow(z, (long long) i * i, mod) % mod;
  259.         }
  260.         return res;
  261.     }
  262. }
  263. #undef double
  264.  
  265. vector<int> Power(vector<int> a, int b) {
  266.     if(b == 1) return a;
  267.     vector<int> ans = Power(a, b / 2);
  268.     ans = FFT::multiply(ans, ans);
  269.     if(b & 1) ans = FFT::multiply(ans, a);
  270.     return ans;
  271. }
  272.  
  273. void solve() {
  274.     int n, k, s, t; cin >> n >> k >> s >> t;
  275.  
  276.     k -= (s % 3 != 1);
  277.     k -= (t % 3 != 1);
  278.     if(k & 1) {
  279.         cout << 0;
  280.         return;
  281.     }
  282.  
  283.     if(k == 0) {
  284.         cout << 1;
  285.         return;
  286.     }
  287.  
  288.     k /= 2;
  289.     vector<int> base;
  290.     base.pb(2);
  291.     base.pb(4);
  292.     base.pb(2);
  293.     vector<int> fft = Power(base, k);
  294.  
  295.     auto distance = [&](int u, int v) -> int {
  296.         assert(u % 3 == 1 && v % 3 == 1);
  297.         if(u > v) swap(u, v);
  298.         v -= u - 1;
  299.         u = 1;
  300.         u = (u + 2) / 3;
  301.         v = (v + 2) / 3;
  302.  
  303.         int ans = 0;
  304.         if(v - u + k < fft.size()) {
  305.             for(int i = 0; v - u + k + i * n < fft.size(); i++) {
  306.                 ans += fft[v - u + k + i * n];
  307.                 if(ans >= MOD) ans -= MOD;
  308.             }
  309.  
  310.             for(int i = 1; v - u + k - i * n >= 0; i++) {
  311.                 ans += fft[v - u + k - i * n];
  312.                 if(ans >= MOD) ans -= MOD;
  313.             }
  314.         }
  315.         return ans;
  316.     };
  317.  
  318.     if(s % 3 == 1 && t % 3 == 1) {
  319.         cout << distance(s, t);
  320.         return;
  321.     }
  322.  
  323.     int ans = 0;
  324.     if(s % 3 != 1 && t % 3 != 1) {
  325.         for(int i = 0; i < 2; i++) {
  326.             for(int j = 0; j < 2; j++) {
  327.                 int u, v;
  328.                 if(s % 3 == 0) {
  329.                     if(i == 0) {
  330.                         u = s - 2;
  331.                     } else u = s % (3 * n) + 1;
  332.                 }
  333.                 if(s % 3 == 2) {
  334.                     if(i == 0) {
  335.                         u = s - 1;
  336.                     } else u = (s + 2) % (3 * n);
  337.                 }
  338.  
  339.                 if(t % 3 == 0) {
  340.                     if(j == 0) {
  341.                         v = t - 2;
  342.                     } else v = t % (3 * n) + 1;
  343.                 }
  344.                 if(t % 3 == 2) {
  345.                     if(j == 0) {
  346.                         v = t - 1;
  347.                     } else v = (t + 2) % (3 * n);
  348.                 }
  349.  
  350.                 ans += distance(u, v);
  351.                 if(ans >= MOD) ans -= MOD;
  352.             }
  353.         }
  354.  
  355.         cout << ans;
  356.         return;
  357.     }
  358.  
  359.     if(s % 3 != 1) swap(s, t);
  360.  
  361.     for(int j = 0; j < 2; j++) {
  362.         int v;
  363.         if(t % 3 == 0) {
  364.             if(j == 0) {
  365.                 v = t - 2;
  366.             } else v = t % (3 * n) + 1;
  367.         }
  368.         if(t % 3 == 2) {
  369.             if(j == 0) {
  370.                 v = t - 1;
  371.             } else v = (t + 2) % (3 * n);
  372.         }
  373.  
  374.         ans += distance(s, v);
  375.         if(ans >= MOD) ans -= MOD;
  376.     }
  377.  
  378.     cout << ans;
  379. }
  380.  
  381. int main()
  382. {
  383.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  384.     #ifndef ONLINE_JUDGE
  385.     freopen("input.txt", "r", stdin);
  386.     freopen("output.txt", "w", stdout);
  387.     #else
  388.     //online
  389.     #endif
  390.  
  391.     int tc = 1, ddd = 0;
  392.     // cin >> tc;
  393.     while(tc--) {
  394.         //ddd++;
  395.         //cout << "Case #" << ddd << ": ";
  396.         solve();
  397.     }
  398. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!