404 Not_Found
给定长度为 (n) 的置换 (p)，判断字符串 (S) 的每个长度为 (n) 的子串再 (p) 下是否为不动点 (|S|, n le 1e5)
首先设置换是 (0, 1, 2, ..., n - 1) 那么置换后的序列 (t_{p_i} =s_i)
考虑使用 (hash) 是否能将两个式子卷起来，用一个点表示一个串的 (hash), (hash) 基数是 (b)
原串 (hash) :
[sum_{i = 0} ^ {n - 1} s_i b^i
]
从 (i) 开始 (n) 个字符的 (hash) 就是
[sum_{j = i} ^ {i + n - 1} s_j b^j
]
从 (i) 开始 (n) 个字符置换后的 (hash) 就是
[sum_{j = i} ^ {i + n - 1} s_j b ^ i b^{j - i} b^{t_{j - i} - (j - i)}
]
设 (c_i = b ^ {t_i - i}) 则式子变成
[sum_{j = i} ^ {i + n - 1} s_j b^j c_{j - i}
]
让 (s_j b^j) 带个 (x^j) 变成多项式 (s_j b^j x^j)，让 (c_i) 带个 (x^{-i}) 变成 (c_i x ^ {-i})，这样两个式子卷起来，(x^i) 的系数就是长度为 (n) 的字符串变换后的 (hash) 值，和原串比较就好了
再说说怎么处理 (c_i x^{-i})，给它乘个 (x^{n - 1}) 相当于把 (c) 序列 (reverse) 后每一项变成 (c_i x ^ i)
乘完之后再除回来就行了
如果你觉着不太可能的化这是测试的代码
#include <bits/stdc++.h>
using namespace std;
#define rg register
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define gc getchar
inline int read(){
rg char ch = gc();
rg int x = 0, f = 0;
while(!isdigit(ch)) f |= (ch == '-'), ch = gc();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return f ? -x : x;
}
const int N = 1e5 + 5, mod = 998244353;
inline void Mod(int &x){
x += (x >> 31) & mod;
}
int a[N], b[N], c[N];
inline void mul(int *a, int *b, int an, int bn, int *c){
// memset(c, 0, (an + 1) * sizeof(int));
rep(i, 0, an)
rep(j, 0, i)
Mod(c[i - j] += 1ll * a[i] * b[j] - mod);
}
inline int ksm(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = 1ll * a * ans % mod;
b >>= 1;
a = 1ll * a * a % mod;
}
return ans;
}
const int G = 3, Gn = ksm(G, mod - 2);
int to[N];
inline void NTT(int *a, int lim, int flag){
for(int i = 0; i < lim; ++i) if(to[i] > i) swap(a[i], a[to[i]]);
for(int l = 2; l <= lim; l <<= 1){
const int m = l >> 1, Gi = ksm(flag == 1 ? G : Gn, (mod - 1) / l);
for(int j = 0; j < lim; j += l){
int g = 1;
for(int i = 0; i < m; ++i, g = 1ll * g * Gi % mod){
int x = a[i + j], y = 1ll * g * a[i + j + m] % mod;
a[i + j] = x + y;
if(a[i + j] >= mod) a[i + j] -= mod;
a[i + j + m] = x + mod - y;
if(a[i + j + m] >= mod) a[i + j + m] -= mod;
}
}
}
}
int n, m;
inline void mul_with_NTT(int *a, int *b, int n, int m,int *c){
int lim = 1, len = 0;
while(lim <= n + m) lim <<= 1, ++len;
for(int i = 1; i < lim; ++i) to[i] = (to[i >> 1] >> 1) | ((i & 1) << len - 1);
NTT(a, lim, 1); NTT(b, lim, 1);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, lim, -1);
const int inv = ksm(lim, mod - 2);
rep(i, 0, n + m) c[i] = 1ll * a[i] * inv % mod;
}
/*
0 1
8
3 1
*/
signed main(){
n = read(), m = read();
rep(i, 0, n) a[i] = read();
rep(i, 0, m) b[i] = read();
// mul(a, b, n, m, c);
// rep(i, 0, n) cout<<c[i]<<" "; cout<<endl;
reverse(b, b + m + 1);
int lim = 1, len = 0;
while(lim <= n + m) lim <<= 1, ++len;
rep(i, 0, lim - 1) to[i] = (to[i >> 1] >> 1) | ((i & 1) << len - 1);
NTT(a, lim, 1); NTT(b, lim, 1);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, lim, -1);
const int inv = ksm(lim, mod - 2);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * inv % mod;
rep(i, m, m + n) cout<<a[i]<<" "; cout<<endl;
gc(), gc();
return 0;
}