#pragma GCC optimize ("O3") #pragma GCC target("avx") #pragma GCC optimize("unroll-loops") #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include // #include // #include // #include // namespace mp = boost::multiprecision; // using Bint=mp::cpp_int; // using Real = mp::number>; // #include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define fi first #define se second #define eb emplace_back // #define endl '\n' #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define debug(v) cout<<#v<<":";for(auto x:v){cout< Point; // Point typedef long long ll; typedef vector vl; typedef vectorvvl; typedef vectorvvvl; typedef vectorvvvvl; typedef vectorvvvvvl; typedef vectorvi; typedef vectorvvi; typedef vectorvvvi; typedef vectorvvvvi; typedef vectorvvvvvi; typedef pair P; // typedef double D; template using minpq=priority_queue,greater>; // const ll MOD=1000000007LL; const ll MOD=998244353LL; const ll mod=MOD; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(bprime_factor(ll n){ mapres; for(ll i=2;i*i<=n;i++){ while(n%i==0){ res[i]++; n/=i; } } if(n!=1)res[n]=1; return res; } const ll MAX = 5000010; long long fac[MAX], finv[MAX], inv[MAX]; //finvが階乗の逆元 // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(ll n, ll k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } ll modpow(ll a, ll n,ll mod=MOD) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } /*Eratosthenes() ll N=2000010; vl arr(N); void Eratosthenes(){ for(ll i = 0; i < N; i++){ arr[i] = 1; } arr[1]=0; for(ll i = 2; i < sqrt(N); i++){ if(arr[i]){ for(ll j = 0; i * (j + 2) < N; j++){ arr[i *(j + 2)] = 0; } } } }*/ //素数判定O(√n) bool is_prime(ll n){ for(ll i=2;i*i<=n;i++){ if(n%i==0)return false; } return n!=1; } //約数の列挙O(√n) vectordivisor(ll n){ vectorres; for(ll i=1;i*i<=n;i++){ if(n%i==0){ res.push_back(i); if(i != n/i) res.push_back(n/i); } } return res; } /* Trie 木: 文字の種類(char_size)、int型で0に対応する文字(base) insert(word): 単語 word を Trie 木に挿入する search(word): 単語 word が Trie 木にあるか判定する start_with(prefix): prefix が一致する単語が Trie 木にあるか判定する count(): 挿入した単語の数を返す size(): Trie 木の頂点数を返す 計算量:insert, search ともに O(M)(Mは単語の長さ) */ template struct Trie { struct Node { // 頂点を表す構造体 vector next; // 子の頂点番号を格納。存在しなければ-1 vector accept; // 末端がこの頂点になる単語の word_id を保存 int c; // base からの間隔をint型で表現したもの int common; // いくつの単語がこの頂点を共有しているか Node(int c_) : c(c_), common(0) { next.assign(char_size, -1); } }; vector nodes; // trie 木本体 int root; Trie() : root(0) { nodes.push_back(Node(root)); } // 単語の挿入 void insert(const string &word, int word_id) { int node_id = 0; for (int i = 0; i < (int)word.size(); i++) { int c = (int)(word[i] - base); int &next_id = nodes[node_id].next[c]; if (next_id == -1) { // 次の頂点が存在しなければ追加 next_id = (int)nodes.size(); nodes.push_back(Node(c)); } ++nodes[node_id].common; node_id = next_id; } ++nodes[node_id].common; nodes[node_id].accept.push_back(word_id); } void insert(const string &word) { insert(word, nodes[0].common); } // 単語とprefixの検索 bool search(const string &word, bool prefix = false) { int node_id = 0; for (int i = 0; i < (int)word.size(); i++) { int c = (int)(word[i] - base); int &next_id = nodes[node_id].next[c]; if (next_id == -1) { // 次の頂点が存在しなければ終了 return false; } node_id = next_id; } return (prefix) ? true : nodes[node_id].accept.size() > 0; } // prefix を持つ単語が存在するかの検索 bool start_with(const string &prefix) { return search(prefix, true); } // 挿入した単語の数 int count() const { return (nodes[0].common); } // Trie木のノード数 int size() const { return ((int)nodes.size()); } }; // //Lowest Common Ancestor // struct Edge{ // int to; // Edge(int to):to(to){} // }; // using Graph = vector>; // class lca { // public: // const int n = 0; // const int log2_n = 0; // vector> parent; // vector depth; // lca() {} // //g:グラフ root:根 // lca(const Graph &g, int root) // : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector(n)), depth(n) { // dfs(g, root, -1, 0); // for (int k = 0; k + 1 < log2_n; k++) { // for (int v = 0; v < (int)g.size(); v++) { // if (parent[k][v] < 0) // parent[k + 1][v] = -1; // else // parent[k + 1][v] = parent[k][parent[k][v]]; // } // } // } // void dfs(const Graph &g, int v, int p, int d) { // parent[0][v] = p; // depth[v] = d; // for (auto &e : g[v]) { // if (e.to != p) dfs(g, e.to, v, d + 1); // } // } // //uとvのlcaを取得 // int get(int u, int v) { // if (depth[u] > depth[v]) swap(u, v); // for (int k = 0; k < log2_n; k++) { // if ((depth[v] - depth[u]) >> k & 1) { // v = parent[k][v]; // } // } // if (u == v) return u; // for (int k = log2_n - 1; k >= 0; k--) { // if (parent[k][u] != parent[k][v]) { // u = parent[k][u]; // v = parent[k][v]; // } // } // return parent[0][u]; // } // int dep(int i) { // return depth[i]; // } // int dist(int u,int v){ // return depth[u]+depth[v]-depth[get(u,v)]*2; // } // }; // union by size + path having class UnionFind { public: vector par; // 各元の親を表す配列 vector siz; // 素集合のサイズを表す配列(1 で初期化) // Constructor UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(ll x, ll y) { // 連結判定 return root(x) == root(y); } ll size(ll x) { // 素集合のサイズ return siz[root(x)]; } }; // 0-indexed parmutation only vvl cycle_partition(const vl &p){ ll n=p.size(); vvl ret; vector check(n,false); rep(i,n)if(!check[p[i]]){ vl v; ll pos=p[i]; v.pb(i); check[i]=true; while(pos!=i){ v.pb(pos); check[pos]=true; pos=p[pos]; } ret.pb(v); } return ret; } vl Z_algorithm(vl s){ ll c=0,n=s.size(); vl Z(n,0); for(ll i=1;i=0 && i+j T pow(T a, long long n, T e = 1) { T ret = e; while (n) { if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; } template struct ModInt { int x; ModInt() : x(0) {} ModInt(long long x_) { if ((x = x_ % mod + mod) >= mod) x -= mod; } ModInt& operator+=(ModInt rhs) { if ((x += rhs.x) >= mod) x -= mod; return *this; } ModInt& operator-=(ModInt rhs) { if ((x -= rhs.x) < 0) x += mod; return *this; } ModInt& operator*=(ModInt rhs) { x = (unsigned long long)x * rhs.x % mod; return *this; } ModInt& operator/=(ModInt rhs) { x = (unsigned long long)x * rhs.inv().x % mod; return *this; } ModInt operator-() const { return -x < 0 ? mod - x : -x; } ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; } ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; } ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; } ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; } bool operator==(ModInt rhs) const { return x == rhs.x; } bool operator!=(ModInt rhs) const { return x != rhs.x; } ModInt inv() const { return pow(*this, mod - 2); } friend ostream& operator<<(ostream& s, ModInt a) { s << a.x; return s; } friend istream& operator>>(istream& s, ModInt& a) { s >> a.x; return s; } }; using mint = ModInt; typedef vector vm; typedef vector >vvm; typedef vector > >vvvm; template struct segment_tree_beats{ int N; vector max1, max2, min1, min2, add, sum; vector maxc, minc, len; void update_max(int i, T x){ sum[i] += (x - max1[i]) * maxc[i]; if (max1[i] == min1[i]){ min1[i] = x; } else if (max1[i] == min2[i]){ min2[i] = x; } max1[i] = x; } void update_min(int i, T x){ sum[i] += (x - min1[i]) * minc[i]; if (min1[i] == max1[i]){ max1[i] = x; } else if (min1[i] == max2[i]){ max2[i] = x; } min1[i] = x; } void update_add(int i, T x){ max1[i] += x; if (max2[i] != -INF){ max2[i] += x; } min1[i] += x; if (min2[i] != INF){ min2[i] += x; } sum[i] += x * len[i]; add[i] += x; } void push(int i){ if (i >= N - 1){ return; } int l = i * 2 + 1; int r = i * 2 + 2; if (add[i] != 0){ update_add(l, add[i]); update_add(r, add[i]); add[i] = 0; } if (max1[i] < max1[l]){ update_max(l, max1[i]); } if (min1[i] > min1[l]){ update_min(l, min1[i]); } if (max1[i] < max1[r]){ update_max(r, max1[i]); } if (min1[i] > min1[r]){ update_min(r, min1[i]); } } void update(int i){ int l = i * 2 + 1; int r = i * 2 + 2; sum[i] = sum[l] + sum[r]; if (max1[l] > max1[r]){ max1[i] = max1[l]; max2[i] = max(max2[l], max1[r]); maxc[i] = maxc[l]; } else if (max1[l] < max1[r]){ max1[i] = max1[r]; max2[i] = max(max1[l], max2[r]); maxc[i] = maxc[r]; } else { max1[i] = max1[l]; max2[i] = max(max2[l], max2[r]); maxc[i] = maxc[l] + maxc[r]; } if (min1[l] < min1[r]){ min1[i] = min1[l]; min2[i] = min(min2[l], min1[r]); minc[i] = minc[l]; } else if (min1[l] > min1[r]){ min1[i] = min1[r]; min2[i] = min(min1[l], min2[r]); minc[i] = minc[r]; } else { min1[i] = min1[l]; min2[i] = min(min2[l], min2[r]); minc[i] = minc[l] + minc[r]; } } segment_tree_beats(vector A){ int n = A.size(); N = 1; while (N < n){ N *= 2; } max1 = vector(N * 2 - 1, -INF); max2 = vector(N * 2 - 1, -INF); min1 = vector(N * 2 - 1, INF); min2 = vector(N * 2 - 1, INF); add = vector(N * 2 - 1, 0); sum = vector(N * 2 - 1, 0); maxc = vector(N * 2 - 1, 1); minc = vector(N * 2 - 1, 1); len = vector(N * 2 - 1, 1); for (int i = 0; i < n; i++){ max1[N - 1 + i] = A[i]; min1[N - 1 + i] = A[i]; sum[N - 1 + i] = A[i]; } for (int i = N - 2; i >= 0; i--){ len[i] = len[i * 2 + 1] + len[i * 2 + 2]; update(i); } } void range_chmin(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l || x >= max1[i]){ return; } else if (L <= l && r <= R && x > max2[i]){ update_max(i, x); return; } push(i); int m = (l + r) / 2; range_chmin(L, R, x, i * 2 + 1, l, m); range_chmin(L, R, x, i * 2 + 2, m, r); update(i); } void range_chmax(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l || x <= min1[i]){ return; } else if (L <= l && r <= R && x < min2[i]){ update_min(i, x); return; } push(i); int m = (l + r) / 2; range_chmax(L, R, x, i * 2 + 1, l, m); range_chmax(L, R, x, i * 2 + 2, m, r); update(i); } void range_add(int L, int R, T x, int i, int l, int r){ if (r <= L || R <= l){ return; } else if (L <= l && r <= R){ update_add(i, x); return; } push(i); int m = (l + r) / 2; range_add(L, R, x, i * 2 + 1, l, m); range_add(L, R, x, i * 2 + 2, m, r); update(i); } T range_sum(int L, int R, int i, int l, int r){ if (r <= L || R <= l){ return 0; } else if (L <= l && r <= R){ return sum[i]; } push(i); int m = (l + r) / 2; return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r); } void range_chmin(int L, int R, T x){ range_chmin(L, R, x, 0, 0, N); } void range_chmax(int L, int R, T x){ range_chmax(L, R, x, 0, 0, N); } void range_add(int L, int R, T x){ range_add(L, R, x, 0, 0, N); } T range_sum(int L, int R){ return range_sum(L, R, 0, 0, N); } }; struct PartiallyPersistentUnionFind { vector par, last; vector > history; PartiallyPersistentUnionFind(ll n) : par(n, -1), last(n, -1), history(n) { for (auto &vec : history) vec.emplace_back(-1, -1); } void init(ll n) { par.assign(n, -1); last.assign(n, -1); history.assign(n, vector

()); for (auto &vec : history) vec.emplace_back(-1, -1); } ll root(ll t, ll x) { if (last[x] == -1 || t < last[x]) return x; return root(t, par[x]); } bool issame(ll t, ll x, ll y) { return root(t, x) == root(t, y); } bool merge(ll t, ll x, ll y) { x = root(t, x); y = root(t, y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; last[y] = t; history[x].emplace_back(t, par[x]); return true; } ll size(ll t, ll x) { x = root(t, x); return -prev(lower_bound(history[x].begin(), history[x].end(), make_pair(t, 0LL)))->second; } }; // matrix template struct Matrix { vector > val; Matrix(int n = 1, int m = 1, T v = 0) : val(n, vector(m, v)) {} void init(int n, int m, T v = 0) {val.assign(n, vector(m, v));} void resize(int n, int m) { val.resize(n); for (int i = 0; i < n; ++i) val[i].resize(m); } Matrix& operator = (const Matrix &A) { val = A.val; return *this; } size_t size() const {return val.size();} vector& operator [] (int i) {return val[i];} const vector& operator [] (int i) const {return val[i];} friend ostream& operator << (ostream& s, const Matrix& M) { s << endl; for (int i = 0; i < (int)M.size(); ++i) s << M[i] << endl; return s; } }; template Matrix operator * (const Matrix &A, const Matrix &B) { Matrix R(A.size(), B[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < B[0].size(); ++j) for (int k = 0; k < B.size(); ++k) R[i][j] += A[i][k] * B[k][j]; return R; } template Matrix pow(const Matrix &A, long long n) { Matrix R(A.size(), A.size()); auto B = A; for (int i = 0; i < A.size(); ++i) R[i][i] = 1; while (n > 0) { if (n & 1) R = R * B; B = B * B; n >>= 1; } return R; } template vector operator * (const Matrix &A, const vector &B) { vector v(A.size()); for (int i = 0; i < A.size(); ++i) for (int k = 0; k < B.size(); ++k) v[i] += A[i][k] * B[k]; return v; } template Matrix operator + (const Matrix &A, const Matrix &B) { Matrix R(A.size(), A[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) R[i][j] = A[i][j] + B[i][j]; return R; } template Matrix operator - (const Matrix &A, const Matrix &B) { Matrix R(A.size(), A[0].size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) R[i][j] = A[i][j] - B[i][j]; return R; } const int MAX_ROW = 510; // to be set appropriately const int MAX_COL = 510; // to be set appropriately struct BitMatrix { int H, W; bitset val[MAX_ROW]; BitMatrix(int m = 1, int n = 1) : H(m), W(n) {} inline bitset& operator [] (int i) {return val[i];} }; int GaussJordan(BitMatrix &A, bool is_extended = false) { int rank = 0; for (int col = 0; col < A.W; ++col) { if (is_extended && col == A.W - 1) break; int pivot = -1; for (int row = rank; row < A.H; ++row) { if (A[row][col]) { pivot = row; break; } } if (pivot == -1) continue; swap(A[pivot], A[rank]); for (int row = 0; row < A.H; ++row) { if (row != rank && A[row][col]) A[row] ^= A[rank]; } ++rank; } return rank; } int linear_equation(BitMatrix A, vector b, vector &res) { int m = A.H, n = A.W; BitMatrix M(m, n + 1); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) M[i][j] = A[i][j]; M[i][n] = b[i]; } int rank = GaussJordan(M, true); // check if it has no solution for (int row = rank; row < m; ++row) if (M[row][n]) return -1; // answer res.assign(n, 0); for (int i = 0; i < rank; ++i) res[i] = M[i][n]; return rank; } ll exp(ll n,ll r){ if(r==0)return 1; return n*exp(n,r-1); } ll factorial(int n){ if(n==0)return 1; return n*factorial(n-1); } void input_vvi(int n){ vectors(n); string ans; ans+="vector> dp={"; rep(i,n){ cin>>s[i]; ans+="{"; ans+=s[i]; ans+="}"; if(i!=n-1)ans+=","; } ans+="};"; cout< power; const uint64_t base; static inline uint64_t add(uint64_t a, uint64_t b) { if((a += b) >= mod) a -= mod; return a; } static inline uint64_t mul(uint64_t a, uint64_t b) { uint128_t c = (uint128_t) a * b; return add(c >> 61, c & mod); } static inline uint64_t generate_base() { mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1); return rand(mt); } inline void expand(size_t sz) { if(power.size() < sz + 1) { int pre_sz = (int) power.size(); power.resize(sz + 1); for(int i = pre_sz - 1; i < sz; i++) { power[i + 1] = mul(power[i], base); } } } explicit RollingHash(uint64_t base = generate_base()) : base(base), power{1} {} vector< uint64_t > build(const string &s) const { int sz = s.size(); vector< uint64_t > hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } template< typename T > vector< uint64_t > build(const vector< T > &s) const { int sz = s.size(); vector< uint64_t > hashed(sz + 1); for(int i = 0; i < sz; i++) { hashed[i + 1] = add(mul(hashed[i], base), s[i]); } return hashed; } uint64_t query(const vector< uint64_t > &s, int l, int r) { expand(r - l); return add(s[r], mod - mul(s[l], power[r - l])); } uint64_t combine(uint64_t h1, uint64_t h2, size_t h2len) { expand(h2len); return add(mul(h1, power[h2len]), h2); } int lcp(const vector< uint64_t > &a, int l1, int r1, const vector< uint64_t > &b, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = 0, high = len + 1; while(high - low > 1) { int mid = (low + high) / 2; if(query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid; else high = mid; } return low; } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(13); //CDEは制約を読もう! //主客転倒!二重和のときは一番内側の物が何回使われるか //√Nで分けるテク //絶対値は外して2通りの式にした後、変数ごとにまとめる //組み合わせが少ないそうなものはdfsで実行してみる(典型25) /*--------------------------------*/ string s;cin>>s; RollingHash roll; auto rhs=roll.build(s); int m;cin>>m; ll cnt=0; int n=s.size(); vector>data(n,vector(11)); rep(i,n){ for(int j=1;j<=10;j++){ if(i+j<=n){ data[i][j]=roll.query(rhs,i,i+j); } } } for(int i=0;i>t; auto rht=roll.build(t); for(int j=0;j+(int)t.size()<=(int)s.size();j++){ if(data[j][t.size()]==roll.query(rht,0,t.size()))cnt++; } } cout<