v 0. Pasted by Anonymous as cpp at 2015-04-08 17:29:09 MSK and set expiration to never.
v 1. Edited by Anonymous as cpp at 2015-04-08 17:35:34 MSK and set expiration to never.

Paste will expire never.

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <utility>
  10. #include <cstdlib>
  11. #include <memory>
  12. #include <queue>
  13. #include <cassert>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <complex>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. #define pb push_back
  22. #define fst first
  23. #define snd second
  24. #define mp make_pair
  25. #define sz(C) ((int) (C).size())
  26. #define forn(i, n) for (int i = 0; i < (int) n; ++i)
  27. #define ford(i, n) for (int i = ((int) n) - 1; i >= 0; --i)
  28. #define y1 gftxdtrtfhyjfctrxujkvbhyjice
  29. #define y0 ehfoiuvhefroerferjhfjkehfjke
  30. #define left sdhfsjkshdjkfsdfgkqqweqweh
  31. #define right yytrwtretywretwreytwreytwr
  32. #define next jskdfksdhfjkdsjksdjkgf
  33. #define prev koeuigrihjdkjdfj
  34. #define hash kjfdkljkdhgjdkfhgurehg
  35. #define all(C) begin(C), end(C)
  36.  
  37. typedef long long ll;
  38. typedef unsigned long long ull;
  39. typedef unsigned int uint;
  40. typedef pair <int,int> pii;
  41. typedef pair <ll, ll> pll;
  42. typedef vector <ll> vll;
  43. typedef vector <int> vi;
  44. typedef vector <vector <int> > vvi;
  45. typedef vector <pii> vii;
  46. typedef long double ld;
  47. typedef complex<ld> cd;
  48. typedef vector<cd> vcd;
  49.  
  50. const ld EPS = 1e-9;
  51. const int MOD = 998244353;
  52. const int MAXN = 1e6 + 10;
  53. const int A = 26;
  54. const ld PI = acos(-1.0);
  55.  
  56. struct TimeStamp {
  57.   string s;
  58.   double start;
  59.  
  60.   TimeStamp(const string& s) : s(s) {
  61.     start = (double) clock() / CLOCKS_PER_SEC;
  62.   }
  63.  
  64.   ~TimeStamp() {
  65.     printf("%s ends in %.5f\n", s.c_str(), (double) clock() / CLOCKS_PER_SEC - start);
  66.   }
  67. };
  68.  
  69. void addmod(int& x, int y, int mod) {
  70.   (x += y) >= mod && (x -= mod);
  71. }
  72.  
  73. int mulmod(int x, int y, int mod) {
  74.   return x * 1ll * y % mod;
  75. }
  76.  
  77. #define ld double
  78.  
  79. namespace FFT {
  80.   struct cd {
  81.     ld a, b;
  82.  
  83.     cd(ld a, ld b) : a(a), b(b) {}
  84.  
  85.     cd(ld x = 0) : a(x), b(0) {}
  86.  
  87.     ld real() const {
  88.       return a;
  89.     }
  90.  
  91.     void operator += (const cd& other) {
  92.       a += other.a;
  93.       b += other.b;
  94.     }
  95.  
  96.     void operator -= (const cd& other) {
  97.       a -= other.a;
  98.       b -= other.b;
  99.     }
  100.  
  101.     void operator *= (const cd& other) {
  102.       tie(a, b) = mp(a * other.a - b * other.b, a * other.b + b * other.a);
  103.     }
  104.  
  105.     friend cd operator * (const cd& x, const cd& y) {
  106.       cd r = x;
  107.       r *= y;
  108.       return r;
  109.     }
  110.  
  111.     friend cd operator + (const cd& x, const cd& y) {
  112.       cd r = x;
  113.       r += y;
  114.       return r;
  115.     }
  116.  
  117.     friend cd operator - (const cd& x, const cd& y) {
  118.       cd r = x;
  119.       r -= y;
  120.       return r;
  121.     }
  122.  
  123.     void operator /= (ld c) {
  124.       a /= c;
  125.       b /= c;
  126.     }
  127.   };
  128.  
  129.   typedef vector<cd> vcd;
  130.  
  131.   const int LOG = 15;
  132.   const int N = 1 << LOG;
  133.  
  134.   int rev[N];
  135.   cd root_[N];
  136.  
  137.   inline cd root(int k, int n) {
  138.     return root_[k * (N / n)];
  139.   }
  140.  
  141.   void precalc() {
  142.     rev[0] = 0;
  143.     int hb = -1;
  144.     for (int i = 1; i < N; ++i) {
  145.       if  ((i & (i - 1)) == 0) {
  146.         ++hb;
  147.       }
  148.       rev[i] = rev[i ^ (1 << hb)] | (1 << (LOG - hb - 1));
  149.     }
  150.  
  151.     forn(i, N) {
  152.       ld ang = PI * i * 2.0 / N;
  153.       root_[i] = cd(cosl(ang), sinl(ang));
  154.     }
  155.   }
  156.  
  157.   void fft_rec(cd* a, int n) {
  158.     if  (n == 1) {
  159.       return;
  160.     }
  161.  
  162.     fft_rec(a, n / 2);
  163.     fft_rec(a + n / 2, n / 2);
  164.    
  165.     forn(k, n / 2) {
  166.       cd w = root(k, n);
  167.       cd x = a[k];
  168.       cd y = w * a[k + n / 2];
  169.       a[k] = x + y;
  170.       a[k + n / 2] = x - y;
  171.     }
  172.   }
  173.  
  174.   void fft(vcd& a) {
  175.     int n = sz(a);
  176.     vcd na(n, cd(0, 0));
  177.     forn(i, n) na[i] = a[rev[i]];
  178.     na.swap(a);
  179.  
  180.     fft_rec(&a[0], n);
  181.   }
  182.  
  183.   void fft_inv(vcd& a) {
  184.     fft(a);
  185.     int n = sz(a);
  186.     reverse(a.begin() + 1, a.end());
  187.     forn(i, n) {
  188.       a[i] /= n;
  189.     }
  190.   }
  191.  
  192.   vi mult(const vi& a, const vi& b) {
  193. //    TimeStamp t("mult");
  194.     vcd A(N, cd(0, 0));
  195.     vcd B(N, cd(0, 0));
  196.     forn(i, sz(a)) A[i] = a[i];
  197.     forn(i, sz(b)) B[i] = b[i];
  198.  
  199.     fft(A);
  200.     fft(B);
  201.  
  202.     forn(i, N) A[i] *= B[i];
  203.  
  204.     fft_inv(A);
  205.  
  206.     vi c(N, 0);
  207.     forn(i, N) c[i] = ((ll) (A[i].real() + 0.5)) % MOD;
  208.  
  209.     return c;
  210.   }
  211.  
  212.   vi multmod(const vi& a, const vi& b) {
  213.     // a = a0 + sqrt(MOD) * a1
  214.     // a = a0 + base * a1
  215.     int base = (int) sqrtl(MOD);
  216.    
  217.     vi a0(sz(a)), a1(sz(a));
  218.     forn(i, sz(a)) {
  219.       a0[i] = a[i] % base;
  220.       a1[i] = a[i] / base;
  221.       assert(a[i] == a0[i] + base * a1[i]);
  222.     }
  223.  
  224.     vi b0(sz(b)), b1(sz(b));
  225.     forn(i, sz(b)) {
  226.       b0[i] = b[i] % base;
  227.       b1[i] = b[i] / base;
  228.       assert(b[i] == b0[i] + base * b1[i]);
  229.     }
  230.  
  231.     vi a01 = a0;
  232.     forn(i, sz(a)) {
  233.       addmod(a01[i], a1[i], MOD)
  234.     }
  235.  
  236.     vi b01 = b0;
  237.     forn(i, sz(b)) {
  238.       addmod(b01[i], b1[i], MOD);
  239.     }
  240.  
  241.     vi C = mult(a01, b01)// 1
  242.  
  243.     vi a0b0 = mult(a0, b0); // 2
  244.     vi a1b1 = mult(a1, b1); // 3
  245.    
  246.     vi mid = C;
  247.     forn(i, N) {
  248.       addmod(mid[i], -a0b0[i] + MOD, MOD);
  249.       addmod(mid[i], -a1b1[i] + MOD, MOD);
  250.     }
  251.  
  252.     vi res = a0b0;
  253.     forn(i, N) {
  254.       addmod(res[i], mulmod(base, mid[i], MOD), MOD);
  255.     }
  256.  
  257.     base = mulmod(base, base, MOD);
  258.     forn(i, N) {
  259.       addmod(res[i], mulmod(base, a1b1[i], MOD), MOD);
  260.     }
  261.      
  262.     return res;
  263.   }
  264. };
  265.  
  266. int P, M;
  267. int p[MAXN];
  268.  
  269. void precalc() {
  270.   p[0] = 1;
  271.   for (int i = 1; i < MAXN; ++i) {
  272.     p[i] = mulmod(p[i - 1], P, M);
  273.   }
  274. }
  275.  
  276. vi solve(int n) {
  277.   if  (n == 0) {
  278.     vi cnt(M, 0);
  279.     cnt[0] = 1;
  280.     return cnt;
  281.   }
  282.  
  283.   if  (n & 1) {
  284.     vi cnt = solve(n - 1);
  285.     vi ncnt(M, 0);
  286.     for (int c = 1; c <= A; ++c) {
  287.       forn(h, sz(cnt)) {
  288.         int new_h = h;
  289.         addmod(new_h, mulmod(c, p[n - 1], M), M);
  290.         addmod(ncnt[new_h], cnt[h], MOD);
  291.       }
  292.     }
  293.     return ncnt;
  294.   }
  295.  
  296.   vi cnt1 = solve(n / 2);
  297.   vi cnt2(M, 0);
  298.   forn(h, sz(cnt1)) {
  299.     int new_h = mulmod(h, p[n / 2], M);
  300.     addmod(cnt2[new_h], cnt1[h], MOD);
  301.   }
  302.  
  303.   vi cnt = FFT::multmod(cnt1, cnt2);
  304.   vi ans(M, 0);
  305.   forn(h, sz(cnt)) {
  306.     addmod(ans[h % M], cnt[h], MOD);
  307.   }
  308.  
  309.   return ans;
  310. }
  311.  
  312. int main() {
  313. #ifdef LOCAL
  314.   freopen(".in", "r", stdin);
  315. //  freopen(".out", "w", stdout);
  316. #endif
  317.  
  318.   int n, x;
  319.   cin >> n >> M >> P >> x;
  320.  
  321.   precalc();
  322.   FFT::precalc();
  323.  
  324.   printf("%d\n", solve(n)[x]);
  325.   return 0;
  326. }