fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MD (1000000007U)
  5. void *wmem;
  6. char memarr[96000000];
  7. template<class T> void malloc1d(T **arr, int x){
  8.   (*arr) = (T*)malloc(x*sizeof(T));
  9. }
  10. template<class T> void free1d(T *arr){
  11.   free(arr);
  12. }
  13. template<class T> void malloc2d(T ***arr, int x, int y){
  14.   int i;
  15.   (*arr) = (T**)malloc(x*sizeof(T*));
  16.   (*arr)[0] = (T*)malloc(x*y*sizeof(T));
  17.   int qSsg05KM = x;
  18.   for(i=(1);i<(qSsg05KM);i++){
  19.     (*arr)[i]=(*arr)[i-1]+y;
  20.   }
  21. }
  22. template<class T> void free2d(T **arr){
  23.   free(arr[0]);
  24.   free(arr);
  25. }
  26. struct Modint{
  27.   unsigned val;
  28.   Modint(){
  29.     val=0;
  30.   }
  31.   Modint(int a){
  32.     val = ord(a);
  33.   }
  34.   Modint(unsigned a){
  35.     val = ord(a);
  36.   }
  37.   Modint(long long a){
  38.     val = ord(a);
  39.   }
  40.   Modint(unsigned long long a){
  41.     val = ord(a);
  42.   }
  43.   inline unsigned ord(unsigned a){
  44.     return a%MD;
  45.   }
  46.   inline unsigned ord(int a){
  47.     a %= (int)MD;
  48.     if(a < 0){
  49.       a += MD;
  50.     }
  51.     return a;
  52.   }
  53.   inline unsigned ord(unsigned long long a){
  54.     return a%MD;
  55.   }
  56.   inline unsigned ord(long long a){
  57.     a %= (int)MD;
  58.     if(a < 0){
  59.       a += MD;
  60.     }
  61.     return a;
  62.   }
  63.   inline unsigned get(){
  64.     return val;
  65.   }
  66.   inline Modint &operator+=(Modint a){
  67.     val += a.val;
  68.     if(val >= MD){
  69.       val -= MD;
  70.     }
  71.     return *this;
  72.   }
  73.   inline Modint &operator-=(Modint a){
  74.     if(val < a.val){
  75.       val = val + MD - a.val;
  76.     }
  77.     else{
  78.       val -= a.val;
  79.     }
  80.     return *this;
  81.   }
  82.   inline Modint &operator*=(Modint a){
  83.     val = ((unsigned long long)val*a.val)%MD;
  84.     return *this;
  85.   }
  86.   inline Modint &operator/=(Modint a){
  87.     return *this *= a.inverse();
  88.   }
  89.   inline Modint operator+(Modint a){
  90.     return Modint(*this)+=a;
  91.   }
  92.   inline Modint operator-(Modint a){
  93.     return Modint(*this)-=a;
  94.   }
  95.   inline Modint operator*(Modint a){
  96.     return Modint(*this)*=a;
  97.   }
  98.   inline Modint operator/(Modint a){
  99.     return Modint(*this)/=a;
  100.   }
  101.   inline Modint operator+(int a){
  102.     return Modint(*this)+=Modint(a);
  103.   }
  104.   inline Modint operator-(int a){
  105.     return Modint(*this)-=Modint(a);
  106.   }
  107.   inline Modint operator*(int a){
  108.     return Modint(*this)*=Modint(a);
  109.   }
  110.   inline Modint operator/(int a){
  111.     return Modint(*this)/=Modint(a);
  112.   }
  113.   inline Modint operator+(long long a){
  114.     return Modint(*this)+=Modint(a);
  115.   }
  116.   inline Modint operator-(long long a){
  117.     return Modint(*this)-=Modint(a);
  118.   }
  119.   inline Modint operator*(long long a){
  120.     return Modint(*this)*=Modint(a);
  121.   }
  122.   inline Modint operator/(long long a){
  123.     return Modint(*this)/=Modint(a);
  124.   }
  125.   inline Modint operator-(void){
  126.     Modint res;
  127.     if(val){
  128.       res.val=MD-val;
  129.     }
  130.     else{
  131.       res.val=0;
  132.     }
  133.     return res;
  134.   }
  135.   inline operator bool(void){
  136.     return val!=0;
  137.   }
  138.   inline operator int(void){
  139.     return get();
  140.   }
  141.   inline operator long long(void){
  142.     return get();
  143.   }
  144.   inline Modint inverse(){
  145.     int a = val;
  146.     int b = MD;
  147.     int u = 1;
  148.     int v = 0;
  149.     int t;
  150.     Modint res;
  151.     while(b){
  152.       t = a / b;
  153.       a -= t * b;
  154.       swap(a, b);
  155.       u -= t * v;
  156.       swap(u, v);
  157.     }
  158.     if(u < 0){
  159.       u += MD;
  160.     }
  161.     res.val = u;
  162.     return res;
  163.   }
  164.   inline Modint pw(unsigned long long b){
  165.     Modint a(*this);
  166.     Modint res;
  167.     res.val = 1;
  168.     while(b){
  169.       if(b&1){
  170.         res *= a;
  171.       }
  172.       b >>= 1;
  173.       a *= a;
  174.     }
  175.     return res;
  176.   }
  177.   inline bool operator==(int a){
  178.     return ord(a)==val;
  179.   }
  180.   inline bool operator!=(int a){
  181.     return ord(a)!=val;
  182.   }
  183. }
  184. ;
  185. inline Modint operator+(int a, Modint b){
  186.   return Modint(a)+=b;
  187. }
  188. inline Modint operator-(int a, Modint b){
  189.   return Modint(a)-=b;
  190. }
  191. inline Modint operator*(int a, Modint b){
  192.   return Modint(a)*=b;
  193. }
  194. inline Modint operator/(int a, Modint b){
  195.   return Modint(a)/=b;
  196. }
  197. inline Modint operator+(long long a, Modint b){
  198.   return Modint(a)+=b;
  199. }
  200. inline Modint operator-(long long a, Modint b){
  201.   return Modint(a)-=b;
  202. }
  203. inline Modint operator*(long long a, Modint b){
  204.   return Modint(a)*=b;
  205. }
  206. inline Modint operator/(long long a, Modint b){
  207.   return Modint(a)/=b;
  208. }
  209. template<class S> struct AhoCorasick_Sum{
  210.   int node;
  211.   int mem;
  212.   int alphabet;
  213.   int **nx;
  214.   int *failed;
  215.   S *sum;
  216.   void init(void){
  217.     int i;
  218.     node = 1;
  219.     for(i=(0);i<(alphabet);i++){
  220.       nx[0][i] = -1;
  221.     }
  222.     failed[0] = 0;
  223.     sum[0] = 0;
  224.   }
  225.   void malloc(const int n, const int k){
  226.     int i;
  227.     malloc2d(&nx,n,k);
  228.     malloc1d(&failed,n);
  229.     malloc1d(&sum,n);
  230.     node = n;
  231.     alphabet = k;
  232.     init();
  233.   }
  234.   void free(void){
  235.     free2d(nx);
  236.     free1d(failed);
  237.     free1d(sum);
  238.   }
  239.   template<class T> void addWord(const T word[], const int len, S val){
  240.     int i;
  241.     int j;
  242.     int k;
  243.     int now = 0;
  244.     for(i=(0);i<(len);i++){
  245.       if(nx[now][word[i]]==-1){
  246.         k = node++;
  247.         nx[now][word[i]] = k;
  248.         for(j=(0);j<(alphabet);j++){
  249.           nx[k][j] = -1;
  250.         }
  251.         sum[k] = 0;
  252.       }
  253.       now = nx[now][word[i]];
  254.     }
  255.     sum[now] += val;
  256.   }
  257.   void construct(void *mem = wmem){
  258.     int i;
  259.     int j;
  260.     int k;
  261.     int now;
  262.     int *q;
  263.     int qs;
  264.     int qe;
  265.     q = (int*) mem;
  266.     qs = qe = 0;
  267.     now = 0;
  268.     for(k=(0);k<(alphabet);k++){
  269.       if(nx[now][k] != -1){
  270.         q[qe++] = nx[now][k];
  271.         failed[ nx[now][k] ] = now;
  272.       }
  273.     }
  274.     while(qs < qe){
  275.       now = q[qs++];
  276.       for(k=(0);k<(alphabet);k++){
  277.         if(nx[now][k] != -1){
  278.           i = failed[now];
  279.           while(i){
  280.             if(nx[i][k] != -1){
  281.               break;
  282.             }
  283.             i = failed[i];
  284.           }
  285.           if(nx[i][k] != -1){
  286.             i = nx[i][k];
  287.           }
  288.           failed[ nx[now][k] ] = i;
  289.           sum[ nx[now][k] ] += sum[i];
  290.           q[qe++] = nx[now][k];
  291.         }
  292.       }
  293.     }
  294.   }
  295.   template<class T> inline int next(const int n, const T c){
  296.     int i;
  297.     int now;
  298.     now = n;
  299.     if(nx[n][c]!=-1){
  300.       return nx[n][c];
  301.     }
  302.     while(now && nx[now][c]==-1){
  303.       now=failed[now];
  304.     }
  305.     if(nx[now][c]!=-1){
  306.       now = nx[now][c];
  307.     }
  308.     return nx[n][c] = now;
  309.   }
  310. }
  311. ;
  312. #define main dummy_main
  313. int main(){
  314.   wmem = memarr;
  315.   return 0;
  316. }
  317. #undef main
  318. Modint dp[501][2][2][51];
  319. class Solution{
  320.   public:
  321.   int findGoodStrings(int n, string s1, string s2, string evil){
  322.     int i, x;
  323.     dummy_main();
  324.     int m = evil.size();
  325.     int e[51];
  326.     int st;
  327.     int ed;
  328.     int sx;
  329.     int sy;
  330.     int sj;
  331.     Modint res = 0;
  332.     AhoCorasick_Sum<int> aho;
  333.     for(i=(0);i<(n);i++){
  334.       {
  335.         auto Q5VJL1cS = ('a');
  336.         s1[i] -= Q5VJL1cS;
  337.         s2[i] -= Q5VJL1cS;
  338.       }
  339.     }
  340.     for(i=(0);i<(m);i++){
  341.       e[i] = evil[i] - 'a';
  342.     }
  343.     aho.malloc(m+1, 26);
  344.     aho.init();
  345.     aho.addWord(e, m, 1);
  346.     aho.construct();
  347.     m = aho.node;
  348.     for(i=(0);i<(n+1);i++){
  349.       int x;
  350.       for(x=(0);x<(2);x++){
  351.         int y;
  352.         for(y=(0);y<(2);y++){
  353.           int j;
  354.           for(j=(0);j<(m);j++){
  355.             dp[i][x][y][j] = 0;
  356.           }
  357.         }
  358.       }
  359.     }
  360.     dp[0][0][0][0] = 1;
  361.     for(i=(0);i<(n);i++){
  362.       int x;
  363.       for(x=(0);x<(2);x++){
  364.         int y;
  365.         for(y=(0);y<(2);y++){
  366.           int j;
  367.           for(j=(0);j<(m);j++){
  368.             int k;
  369.             if(x){
  370.               st =0;
  371.             }
  372.             else{
  373.               st =s1[i];
  374.             }
  375.             if(y){
  376.               ed =25;
  377.             }
  378.             else{
  379.               ed =s2[i];
  380.             }
  381.             for(k=(st);k<(ed+1);k++){
  382.               sj = aho.next(j, k);
  383.               if(aho.sum[sj]){
  384.                 continue;
  385.               }
  386.               if(k > s1[i]){
  387.                 sx =1;
  388.               }
  389.               else{
  390.                 sx =x;
  391.               }
  392.               if(k < s2[i]){
  393.                 sy =1;
  394.               }
  395.               else{
  396.                 sy =y;
  397.               }
  398.               dp[i+1][sx][sy][sj] += dp[i][x][y][j];
  399.             }
  400.           }
  401.         }
  402.       }
  403.     }
  404.     for(x=(0);x<(2);x++){
  405.       int y;
  406.       for(y=(0);y<(2);y++){
  407.         int j;
  408.         for(j=(0);j<(m);j++){
  409.           res += dp[n][x][y][j];
  410.         }
  411.       }
  412.     }
  413.     aho.free();
  414.     return res;
  415.   }
  416. }
  417. ;
  418. // cLay varsion 20200325-1
  419.  
  420. // --- original code ---
  421. // #define main dummy_main
  422. // {}
  423. // #undef main
  424. // 
  425. // Modint dp[501][2][2][51];
  426. // 
  427. // class Solution {
  428. // public:
  429. //   int findGoodStrings(int n, string s1, string s2, string evil) {
  430. //     dummy_main();
  431. // 
  432. //     int m = evil.size(), e[51];
  433. //     int st, ed, sx, sy, sj;
  434. //     Modint res = 0;
  435. // 
  436. //     AhoCorasick_Sum<int> aho;
  437. //     rep(i,n) (s1[i], s2[i]) -= 'a';
  438. //     rep(i,m) e[i] = evil[i] - 'a';
  439. //     aho.malloc(m+1, 26);
  440. //     aho.init();
  441. //     aho.addWord(e, m, 1);
  442. //     aho.construct();
  443. //     m = aho.node;
  444. // 
  445. //     rep(i,n+1) rep(x,2) rep(y,2) rep(j,m) dp[i][x][y][j] = 0;
  446. //     dp[0][0][0][0] = 1;
  447. // 
  448. //     rep(i,n) rep(x,2) rep(y,2) rep(j,m){
  449. //       st = if[x,0,s1[i]];
  450. //       ed = if[y,25,s2[i]];
  451. //       rep(k,st,ed+1){
  452. //         sj = aho.next(j, k);
  453. //         if(aho.sum[sj]) continue;
  454. //         sx = if[k > s1[i], 1, x];
  455. //         sy = if[k < s2[i], 1, y];
  456. //         dp[i+1][sx][sy][sj] += dp[i][x][y][j];
  457. //       }
  458. //     }
  459. //     rep(x,2) rep(y,2) rep(j,m) res += dp[n][x][y][j];
  460. // 
  461. //     aho.free();
  462. //     return res;
  463. //   }
  464. // };
  465.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/vmIT0y
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!