#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// ULL P,B; vector< vector > bmp(26,vector(100001) ); ULL kake(ULL A, int n){ //A*n ULL ret=0; for(int bit=31;bit>=0;--bit){ ret = (ret + ret) % P; if( n & (1 << bit) ){ ret = (ret + A) % P; } } return ret; } void initbmp(){ bmp[0][0] = 1; bmp[0][1] = B % P; for(int i=2;i<100001;++i){ bmp[0][i] = ( bmp[0][i-1] * B ) % P; } ULL add; for(int i=0;i<100001;++i){ add = bmp[0][i]; bmp[0][i] = kake( bmp[0][i], 97 ); for(int j=1;j<26;++j){ bmp[j][i] = ( bmp[j-1][i] + add ) % P; } } } ULL calH(string &str){ int len = str.size(); ULL ret = 0; for(int i=0;i &v ){ int len = v.size(); ULL ret = 0; for(int i=0;i= P ){ ret = ret % P; } } } return ret; } void show( vector &v ){ char c; int len = v.size(); for(int i=0;i> P >> B; initbmp(); ULL ah,bh; const int Lmax = 10000; vector S(Lmax,0); vector T(Lmax,0); random_device rnd; mt19937 mt(rnd()); for(int i=0;i