fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (998244353U)
  5. #define MINT_W (32U)
  6. #define MINT_R (301989884U)
  7. #define MINT_RR (932051910U)
  8. #define MINT_MDNINV (998244351U)
  9. #define MD_PRIMITIVE_ROOT (3U)
  10. #define PI 3.14159265358979323846
  11. void*wmem;
  12. char memarr[96000000];
  13. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  14.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  15.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  16.   (*arr)=(T*)(*mem);
  17.   (*mem)=((*arr)+x);
  18. }
  19. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  20.   walloc1d(arr, x2-x1, mem);
  21.   (*arr) -= x1;
  22. }
  23. struct Mint{
  24.   unsigned val;
  25.   Mint(){
  26.     val=0;
  27.   }
  28.   Mint(int a){
  29.     val = mulR(a);
  30.   }
  31.   Mint(unsigned a){
  32.     val = mulR(a);
  33.   }
  34.   Mint(long long a){
  35.     val = mulR(a);
  36.   }
  37.   Mint(unsigned long long a){
  38.     val = mulR(a);
  39.   }
  40.   inline unsigned mulR(unsigned a){
  41.     return (unsigned long long)a*MINT_R%MD;
  42.   }
  43.   inline unsigned mulR(int a){
  44.     if(a < 0){
  45.       a = a%((int)MD)+(int)MD;
  46.     }
  47.     return mulR((unsigned)a);
  48.   }
  49.   inline unsigned mulR(unsigned long long a){
  50.     return mulR((unsigned)(a%MD));
  51.   }
  52.   inline unsigned mulR(long long a){
  53.     a %= (int)MD;
  54.     if(a < 0){
  55.       a += MD;
  56.     }
  57.     return mulR((unsigned)a);
  58.   }
  59.   inline unsigned reduce(unsigned T){
  60.     unsigned m = T * MINT_MDNINV;
  61.     unsigned t = (unsigned)((T + (unsigned long long)m*MD) >> MINT_W);
  62.     if(t >= MD){
  63.       t -= MD;
  64.     }
  65.     return t;
  66.   }
  67.   inline unsigned reduce(unsigned long long T){
  68.     unsigned m = (unsigned)T * MINT_MDNINV;
  69.     unsigned t = (unsigned)((T + (unsigned long long)m*MD) >> MINT_W);
  70.     if(t >= MD){
  71.       t -= MD;
  72.     }
  73.     return t;
  74.   }
  75.   inline unsigned get(){
  76.     return reduce(val);
  77.   }
  78.   inline Mint &operator+=(Mint a){
  79.     val += a.val;
  80.     if(val >= MD){
  81.       val -= MD;
  82.     }
  83.     return *this;
  84.   }
  85.   inline Mint &operator-=(Mint a){
  86.     if(val < a.val){
  87.       val = val + MD - a.val;
  88.     }
  89.     else{
  90.       val -= a.val;
  91.     }
  92.     return *this;
  93.   }
  94.   inline Mint &operator*=(Mint a){
  95.     val = reduce((unsigned long long)val*a.val);
  96.     return *this;
  97.   }
  98.   inline Mint &operator/=(Mint a){
  99.     return *this *= a.inverse();
  100.   }
  101.   inline Mint operator+(Mint a){
  102.     return Mint(*this)+=a;
  103.   }
  104.   inline Mint operator-(Mint a){
  105.     return Mint(*this)-=a;
  106.   }
  107.   inline Mint operator*(Mint a){
  108.     return Mint(*this)*=a;
  109.   }
  110.   inline Mint operator/(Mint a){
  111.     return Mint(*this)/=a;
  112.   }
  113.   inline Mint operator+(int a){
  114.     return Mint(*this)+=Mint(a);
  115.   }
  116.   inline Mint operator-(int a){
  117.     return Mint(*this)-=Mint(a);
  118.   }
  119.   inline Mint operator*(int a){
  120.     return Mint(*this)*=Mint(a);
  121.   }
  122.   inline Mint operator/(int a){
  123.     return Mint(*this)/=Mint(a);
  124.   }
  125.   inline Mint operator+(long long a){
  126.     return Mint(*this)+=Mint(a);
  127.   }
  128.   inline Mint operator-(long long a){
  129.     return Mint(*this)-=Mint(a);
  130.   }
  131.   inline Mint operator*(long long a){
  132.     return Mint(*this)*=Mint(a);
  133.   }
  134.   inline Mint operator/(long long a){
  135.     return Mint(*this)/=Mint(a);
  136.   }
  137.   inline Mint operator-(void){
  138.     Mint res;
  139.     if(val){
  140.       res.val=MD-val;
  141.     }
  142.     else{
  143.       res.val=0;
  144.     }
  145.     return res;
  146.   }
  147.   inline operator bool(void){
  148.     return val!=0;
  149.   }
  150.   inline operator int(void){
  151.     return get();
  152.   }
  153.   inline operator long long(void){
  154.     return get();
  155.   }
  156.   inline Mint inverse(){
  157.     int a = val;
  158.     int b = MD;
  159.     int u = 1;
  160.     int v = 0;
  161.     int t;
  162.     Mint res;
  163.     while(b){
  164.       t = a / b;
  165.       a -= t * b;
  166.       swap(a, b);
  167.       u -= t * v;
  168.       swap(u, v);
  169.     }
  170.     if(u < 0){
  171.       u += MD;
  172.     }
  173.     res.val = (unsigned long long)u*MINT_RR % MD;
  174.     return res;
  175.   }
  176.   inline Mint pw(unsigned long long b){
  177.     Mint a(*this);
  178.     Mint res;
  179.     res.val = MINT_R;
  180.     while(b){
  181.       if(b&1){
  182.         res *= a;
  183.       }
  184.       b >>= 1;
  185.       a *= a;
  186.     }
  187.     return res;
  188.   }
  189.   inline bool operator==(int a){
  190.     return mulR(a)==val;
  191.   }
  192.   inline bool operator!=(int a){
  193.     return mulR(a)!=val;
  194.   }
  195. }
  196. ;
  197. inline Mint operator+(int a, Mint b){
  198.   return Mint(a)+=b;
  199. }
  200. inline Mint operator-(int a, Mint b){
  201.   return Mint(a)-=b;
  202. }
  203. inline Mint operator*(int a, Mint b){
  204.   return Mint(a)*=b;
  205. }
  206. inline Mint operator/(int a, Mint b){
  207.   return Mint(a)/=b;
  208. }
  209. inline Mint operator+(long long a, Mint b){
  210.   return Mint(a)+=b;
  211. }
  212. inline Mint operator-(long long a, Mint b){
  213.   return Mint(a)-=b;
  214. }
  215. inline Mint operator*(long long a, Mint b){
  216.   return Mint(a)*=b;
  217. }
  218. inline Mint operator/(long long a, Mint b){
  219.   return Mint(a)/=b;
  220. }
  221. inline int my_getchar_unlocked(){
  222.   static char buf[1048576];
  223.   static int s = 1048576;
  224.   static int e = 1048576;
  225.   if(s == e && e == 1048576){
  226.     e = fread_unlocked(buf, 1, 1048576, stdin);
  227.     s = 0;
  228.   }
  229.   if(s == e){
  230.     return EOF;
  231.   }
  232.   return buf[s++];
  233. }
  234. inline void rd(int &x){
  235.   int k;
  236.   int m=0;
  237.   x=0;
  238.   for(;;){
  239.     k = my_getchar_unlocked();
  240.     if(k=='-'){
  241.       m=1;
  242.       break;
  243.     }
  244.     if('0'<=k&&k<='9'){
  245.       x=k-'0';
  246.       break;
  247.     }
  248.   }
  249.   for(;;){
  250.     k = my_getchar_unlocked();
  251.     if(k<'0'||k>'9'){
  252.       break;
  253.     }
  254.     x=x*10+k-'0';
  255.   }
  256.   if(m){
  257.     x=-x;
  258.   }
  259. }
  260. inline void rd(char &c){
  261.   int i;
  262.   for(;;){
  263.     i = my_getchar_unlocked();
  264.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  265.       break;
  266.     }
  267.   }
  268.   c = i;
  269. }
  270. inline int rd(char c[]){
  271.   int i;
  272.   int sz = 0;
  273.   for(;;){
  274.     i = my_getchar_unlocked();
  275.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  276.       break;
  277.     }
  278.   }
  279.   c[sz++] = i;
  280.   for(;;){
  281.     i = my_getchar_unlocked();
  282.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  283.       break;
  284.     }
  285.     c[sz++] = i;
  286.   }
  287.   c[sz]='\0';
  288.   return sz;
  289. }
  290. struct MY_WRITER{
  291.   char buf[1048576];
  292.   int s;
  293.   int e;
  294.   MY_WRITER(){
  295.     s = 0;
  296.     e = 1048576;
  297.   }
  298.   ~MY_WRITER(){
  299.     if(s){
  300.       fwrite_unlocked(buf, 1, s, stdout);
  301.     }
  302.   }
  303. }
  304. ;
  305. MY_WRITER MY_WRITER_VAR;
  306. void my_putchar_unlocked(int a){
  307.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  308.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  309.     MY_WRITER_VAR.s = 0;
  310.   }
  311.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  312. }
  313. inline void wt_L(char a){
  314.   my_putchar_unlocked(a);
  315. }
  316. inline void wt_L(int x){
  317.   int s=0;
  318.   int m=0;
  319.   char f[10];
  320.   if(x<0){
  321.     m=1;
  322.     x=-x;
  323.   }
  324.   while(x){
  325.     f[s++]=x%10;
  326.     x/=10;
  327.   }
  328.   if(!s){
  329.     f[s++]=0;
  330.   }
  331.   if(m){
  332.     my_putchar_unlocked('-');
  333.   }
  334.   while(s--){
  335.     my_putchar_unlocked(f[s]+'0');
  336.   }
  337. }
  338. inline void wt_L(Mint x){
  339.   int i;
  340.   i = (int)x;
  341.   wt_L(i);
  342. }
  343. template<class T, class S> inline T pow_L(T a, S b){
  344.   T res = 1;
  345.   res = 1;
  346.   for(;;){
  347.     if(b&1){
  348.       res *= a;
  349.     }
  350.     b >>= 1;
  351.     if(b==0){
  352.       break;
  353.     }
  354.     a *= a;
  355.   }
  356.   return res;
  357. }
  358. inline double pow_L(double a, double b){
  359.   return pow(a,b);
  360. }
  361. struct fft_pnt{
  362.   double x;
  363.   double y;
  364.   fft_pnt(void){
  365.   }
  366.   fft_pnt(double a, double b){
  367.     x = a;
  368.     y = b;
  369.   }
  370.   void set(double a, double b){
  371.     x = a;
  372.     y = b;
  373.   }
  374.   fft_pnt& operator+=(fft_pnt a){
  375.     x+=a.x;
  376.     y+=a.y;
  377.     return *this;
  378.   }
  379.   fft_pnt& operator-=(fft_pnt a){
  380.     x-=a.x;
  381.     y-=a.y;
  382.     return *this;
  383.   }
  384.   fft_pnt& operator*=(fft_pnt a){
  385.     fft_pnt p = *this;
  386.     x = p.x*a.x-p.y*a.y;
  387.     y = p.x*a.y+p.y*a.x;
  388.     return *this;
  389.   }
  390.   fft_pnt operator+(fft_pnt a){
  391.     return fft_pnt(*this) += a;
  392.   }
  393.   fft_pnt operator-(fft_pnt a){
  394.     return fft_pnt(*this) -= a;
  395.   }
  396.   fft_pnt operator*(fft_pnt a){
  397.     return fft_pnt(*this) *= a;
  398.   }
  399. }
  400. ;
  401. void fft(int n, fft_pnt x[], void *mem = wmem){
  402.   int i;
  403.   int j;
  404.   int n1;
  405.   int n2;
  406.   int n3;
  407.   int step = 1;
  408.   double theta = 2*PI / n;
  409.   double tmp;
  410.   fft_pnt w1;
  411.   fft_pnt w2;
  412.   fft_pnt w3;
  413.   fft_pnt a;
  414.   fft_pnt b;
  415.   fft_pnt c;
  416.   fft_pnt d;
  417.   fft_pnt aa;
  418.   fft_pnt bb;
  419.   fft_pnt cc;
  420.   fft_pnt dd;
  421.   fft_pnt*y = (fft_pnt*)mem;
  422.   while(n > 2){
  423.     n1 = n / 4;
  424.     n2 = n1 + n1;
  425.     n3 = n1 + n2;
  426.     for(i=(0);i<(n1);i++){
  427.       w1 = fft_pnt(cos(i*theta),-sin(i*theta));
  428.       w2 = w1*w1;
  429.       w3 = w1*w2;
  430.       for(j=(0);j<(step);j++){
  431.         a = x[j+step*i];
  432.         b = x[j+step*(i+n1)];
  433.         c = x[j+step*(i+n2)];
  434.         d = x[j+step*(i+n3)];
  435.         aa = a + c;
  436.         bb = a - c;
  437.         cc = b + d;
  438.         dd = b - d;
  439.         tmp = dd.y;
  440.         dd.y = dd.x;
  441.         dd.x = -tmp;
  442.         y[j+step*(4*i  )] = aa + cc;
  443.         y[j+step*(4*i+1)] = w1*(bb - dd);
  444.         y[j+step*(4*i+2)] = w2*(aa - cc);
  445.         y[j+step*(4*i+3)] = w3*(bb + dd);
  446.       }
  447.     }
  448.     n /= 4;
  449.     step *= 4;
  450.     theta *= 4;
  451.     swap(x,y);
  452.   }
  453.   if(n==2){
  454.     for(i=(0);i<(step);i++){
  455.       y[i] = x[i] + x[i+step];
  456.       y[i+step] = x[i] - x[i+step];
  457.     }
  458.     n /= 2;
  459.     step *= 2;
  460.     theta *= 2;
  461.     swap(x,y);
  462.   }
  463.   for(i=(0);i<(step);i++){
  464.     y[i] = x[i];
  465.   }
  466. }
  467. void fftinv(int n, fft_pnt x[], void *mem = wmem){
  468.   int i;
  469.   int j;
  470.   int n1;
  471.   int n2;
  472.   int n3;
  473.   int step = 1;
  474.   double theta = 2*PI / n;
  475.   double tmp;
  476.   fft_pnt w1;
  477.   fft_pnt w2;
  478.   fft_pnt w3;
  479.   fft_pnt a;
  480.   fft_pnt b;
  481.   fft_pnt c;
  482.   fft_pnt d;
  483.   fft_pnt aa;
  484.   fft_pnt bb;
  485.   fft_pnt cc;
  486.   fft_pnt dd;
  487.   fft_pnt*y = (fft_pnt*)mem;
  488.   while(n > 2){
  489.     n1 = n / 4;
  490.     n2 = n1 + n1;
  491.     n3 = n1 + n2;
  492.     for(i=(0);i<(n1);i++){
  493.       w1 = fft_pnt(cos(i*theta),sin(i*theta));
  494.       w2 = w1*w1;
  495.       w3 = w1*w2;
  496.       for(j=(0);j<(step);j++){
  497.         a = x[j+step*i];
  498.         b = x[j+step*(i+n1)];
  499.         c = x[j+step*(i+n2)];
  500.         d = x[j+step*(i+n3)];
  501.         aa = a + c;
  502.         bb = a - c;
  503.         cc = b + d;
  504.         dd = b - d;
  505.         tmp = dd.y;
  506.         dd.y = dd.x;
  507.         dd.x = -tmp;
  508.         y[j+step*(4*i  )] = aa + cc;
  509.         y[j+step*(4*i+1)] = w1*(bb + dd);
  510.         y[j+step*(4*i+2)] = w2*(aa - cc);
  511.         y[j+step*(4*i+3)] = w3*(bb - dd);
  512.       }
  513.     }
  514.     n /= 4;
  515.     step *= 4;
  516.     theta *= 4;
  517.     swap(x,y);
  518.   }
  519.   if(n==2){
  520.     for(i=(0);i<(step);i++){
  521.       y[i] = x[i] + x[i+step];
  522.       y[i+step] = x[i] - x[i+step];
  523.     }
  524.     n /= 2;
  525.     step *= 2;
  526.     theta *= 2;
  527.     swap(x,y);
  528.   }
  529.   for(i=(0);i<(step);i++){
  530.     y[i] = x[i];
  531.   }
  532. }
  533. void fft(int n, Mint x[], Mint root = MD_PRIMITIVE_ROOT, void *mem = wmem){
  534.   int i;
  535.   int j;
  536.   int n1;
  537.   int n2;
  538.   int n3;
  539.   int step = 1;
  540.   Mint w1;
  541.   Mint w2;
  542.   Mint w3;
  543.   Mint a;
  544.   Mint b;
  545.   Mint c;
  546.   Mint d;
  547.   Mint aa;
  548.   Mint bb;
  549.   Mint cc;
  550.   Mint dd;
  551.   Mint tmp;
  552.   Mint*y;
  553.   walloc1d(&y, n, &mem);
  554.   tmp = root.pw((MD-1)/4*3);
  555.   root = root.pw((MD-1)/n);
  556.   while(n > 2){
  557.     n1 = n / 4;
  558.     n2 = n1 + n1;
  559.     n3 = n1 + n2;
  560.     w1.val = MINT_R;
  561.     for(i=(0);i<(n1);i++){
  562.       w2 = w1*w1;
  563.       w3 = w1*w2;
  564.       for(j=(0);j<(step);j++){
  565.         a = x[j+step*i];
  566.         b = x[j+step*(i+n1)];
  567.         c = x[j+step*(i+n2)];
  568.         d = x[j+step*(i+n3)];
  569.         aa = a + c;
  570.         bb = a - c;
  571.         cc = b + d;
  572.         dd = (b - d) * tmp;
  573.         y[j+step*(4*i  )] = aa + cc;
  574.         y[j+step*(4*i+1)] = w1*(bb - dd);
  575.         y[j+step*(4*i+2)] = w2*(aa - cc);
  576.         y[j+step*(4*i+3)] = w3*(bb + dd);
  577.       }
  578.       w1 *= root;
  579.     }
  580.     n /= 4;
  581.     step *= 4;
  582.     root *= root;
  583.     root *= root;
  584.     swap(x,y);
  585.   }
  586.   if(n==2){
  587.     for(i=(0);i<(step);i++){
  588.       y[i] = x[i] + x[i+step];
  589.       y[i+step] = x[i] - x[i+step];
  590.     }
  591.     n /= 2;
  592.     step *= 2;
  593.     root *= root;
  594.     swap(x,y);
  595.   }
  596.   for(i=(0);i<(step);i++){
  597.     y[i] = x[i];
  598.   }
  599. }
  600. void fftinv(int n, Mint x[], Mint root = MD_PRIMITIVE_ROOT, void *mem = wmem){
  601.   int i;
  602.   int j;
  603.   int n1;
  604.   int n2;
  605.   int n3;
  606.   int step = 1;
  607.   Mint w1;
  608.   Mint w2;
  609.   Mint w3;
  610.   Mint a;
  611.   Mint b;
  612.   Mint c;
  613.   Mint d;
  614.   Mint aa;
  615.   Mint bb;
  616.   Mint cc;
  617.   Mint dd;
  618.   Mint tmp;
  619.   Mint*y;
  620.   walloc1d(&y, n, &mem);
  621.   root = root.inverse();
  622.   tmp = root.pw((MD-1)/4);
  623.   root = root.pw((MD-1)/n);
  624.   while(n > 2){
  625.     n1 = n / 4;
  626.     n2 = n1 + n1;
  627.     n3 = n1 + n2;
  628.     w1.val = MINT_R;
  629.     for(i=(0);i<(n1);i++){
  630.       w2 = w1*w1;
  631.       w3 = w1*w2;
  632.       for(j=(0);j<(step);j++){
  633.         a = x[j+step*i];
  634.         b = x[j+step*(i+n1)];
  635.         c = x[j+step*(i+n2)];
  636.         d = x[j+step*(i+n3)];
  637.         aa = a + c;
  638.         bb = a - c;
  639.         cc = b + d;
  640.         dd = (b - d) * tmp;
  641.         y[j+step*(4*i  )] = aa + cc;
  642.         y[j+step*(4*i+1)] = w1*(bb + dd);
  643.         y[j+step*(4*i+2)] = w2*(aa - cc);
  644.         y[j+step*(4*i+3)] = w3*(bb - dd);
  645.       }
  646.       w1 *= root;
  647.     }
  648.     n /= 4;
  649.     step *= 4;
  650.     root *= root;
  651.     root *= root;
  652.     swap(x,y);
  653.   }
  654.   if(n==2){
  655.     for(i=(0);i<(step);i++){
  656.       y[i] = x[i] + x[i+step];
  657.       y[i+step] = x[i] - x[i+step];
  658.     }
  659.     n /= 2;
  660.     step *= 2;
  661.     root *= root;
  662.     swap(x,y);
  663.   }
  664.   for(i=(0);i<(step);i++){
  665.     y[i] = x[i];
  666.   }
  667. }
  668. int N;
  669. int M;
  670. int T;
  671. int K;
  672. char F[100000+2];
  673. char S[100000+2];
  674. int bc;
  675. int sc;
  676. int trial;
  677. int big[100000];
  678. int small[100000];
  679. Mint arr1[7][270000];
  680. Mint arr2[7][270000];
  681. Mint arr[270000];
  682. int main(){
  683.   int c, i, r;
  684.   wmem = memarr;
  685.   Mint res = 0;
  686.   Mint v;
  687.   rd(N);
  688.   rd(M);
  689.   rd(T);
  690.   rd(K);
  691.   rd(F);
  692.   rd(S);
  693.   for(i=(0);i<(N);i++){
  694.     F[i] -= 'A';
  695.   }
  696.   for(i=(0);i<(K);i++){
  697.     S[i] -= 'A';
  698.   }
  699.   trial = N - K + 1;
  700.   sc = M / T;
  701.   bc = sc + 1;
  702.   for(i=(0);i<(N);i++){
  703.     arr1[F[i]][i] = 1;
  704.   }
  705.   for(i=(0);i<(K);i++){
  706.     arr2[S[K-1-i]][i] = 1;
  707.   }
  708.   for(c=(0);c<(T);c++){
  709.     fft(1<<18, arr1[c]);
  710.   }
  711.   for(c=(0);c<(T);c++){
  712.     fft(1<<18, arr2[c]);
  713.   }
  714.   int tU__gIr_ = M%T;
  715.   for(r=(0);r<(tU__gIr_);r++){
  716.     for(c=(0);c<(T);c++){
  717.       for(i=(0);i<(1<<18);i++){
  718.         arr[i] += arr1[c][i] * arr2[(c+r)%T][i];
  719.       }
  720.     }
  721.   }
  722.   fftinv(1<<18, arr);
  723.   v = 1 / Mint(1<<18);
  724.   for(i=(0);i<(trial);i++){
  725.     big[i] = (int)(arr[K-1+i] * v);
  726.   }
  727.   for(i=(0);i<(trial);i++){
  728.     small[i] = K - big[i];
  729.   }
  730.   for(i=(0);i<(trial);i++){
  731.     res += ((pow_L(Mint(sc),small[i]))) * ((pow_L(Mint(bc),big[i])));
  732.   }
  733.   wt_L(res);
  734.   wt_L('\n');
  735.   return 0;
  736. }
  737. // cLay version 20201227-1
  738.  
  739. // --- original code ---
  740. // #define MD 998244353
  741. // int N, M, T, K;
  742. // char F[1d5+2], S[1d5+2];
  743. // 
  744. // int bc, sc, trial;
  745. // int big[1d5], small[1d5];
  746. // Mint arr1[7][2.7d5], arr2[7][2.7d5], arr[2.7d5];
  747. // {
  748. //   Mint res = 0, v;
  749. //   rd(N,M,T,K,F,S);
  750. //   rep(i,N) F[i] -= 'A';
  751. //   rep(i,K) S[i] -= 'A';
  752. //   
  753. //   trial = N - K + 1;
  754. //   sc = M / T;
  755. //   bc = sc + 1;
  756. // 
  757. //   rep(i,N) arr1[F[i]][i] = 1;
  758. //   rep(i,K) arr2[S[K-1-i]][i] = 1;
  759. //   rep(c,T) fft(1<<18, arr1[c]);
  760. //   rep(c,T) fft(1<<18, arr2[c]);
  761. //   REP(r,M%T) rep(c,T) rep(i,1<<18) arr[i] += arr1[c][i] * arr2[(c+r)%T][i];
  762. // 
  763. //   fftinv(1<<18, arr);
  764. //   v = 1 / Mint(1<<18);
  765. //   rep(i,trial) big[i] = (int)(arr[K-1+i] * v);
  766. //   rep(i,trial) small[i] = K - big[i];
  767. //   rep(i,trial) res += (Mint(sc) ** small[i]) * (Mint(bc) ** big[i]);
  768. //   wt(res);
  769. // }
  770.  
Time limit exceeded #stdin #stdout 5s 19048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hla0NA
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!