省选测试 10
T1
原题不硕了.
T2
给一个长度为\(n\)的字符串\(S\)，有\(n-2\)次修改操作，第\(i\)次操作会将第\(i+1\)个字符变成\(w_i\)。
你需要在每次操作之后(包括未操作时)输出这个字符串的最长回文子串，即修改对后续有影响。
对于你来说，只需要输出一个\(ans\)，表示每次操作之后的答案的最大值就可以了。
\(n <= 1e5\)
Manacher + 二分 + Hash.
转化后的题面 : 给定一个字符串\(A\)和一个字符串\(B\).然后选出最长的是回文串的\(A_i-A_j+B_{j+1}-B_k\)这一段字符串.
我们可以知道 : 符合条件的字符串一定是中间一段是回文串, 左右两边是长度相等的反串.对于中间那个回文串, 我们跑一边Manacher就可以得到了, 然后两边的直接用二分加Hash去判断.
这样并不会枚举到所有的合法回文串, 但是我们贪心的选取了中间一段最长的, 然后再向两边扩展, 就可以得到最大的答案了.
\(O(n\log n)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
int n, ans;
int r_[N];
char s[N], ch1[N], ch2[N];
void Manacher(int f) {
int len = 0, mx = 0, p = 0;
s[++ len] = '$';
if(f == 1) for(int i = 1;i <= n; i++) s[i * 2] = '#', s[i * 2 + 1] = ch1[i];
if(f == 2) for(int i = 1;i <= n; i++) s[i * 2] = '#', s[i * 2 + 1] = ch2[i];
len = n * 2 + 1; s[++ len] = '#'; s[++ len] = '@';
for(int i = 1;i <= len; i++) {
if(i > mx) r_[i] = 1;
else r_[i] = min(r_[2 * p - i], mx - i + 1);
while(s[i + r_[i]] == s[i - r_[i]]) r_[i] ++;
if(i + r_[i] - 1 > mx) mx = i + r_[i] - 1, p = i;
ans = max(ans, r_[i] - 1);
// if(s[i] != '$' && s[i] != '@') cout << i << " " << s[i] << " " << r_[i] << "\n";
}
}
const int B = 233, mod = 998244353;
unsigned long long h1[N], h2[N], pow_B[N];
void Hash() {
for(int i = 1;i <= n; i++) h1[i] = h1[i - 1] * B + ch1[i];
reverse(ch2 + 1, ch2 + n + 1);
for(int i = 1;i <= n; i++) h2[i] = h2[i - 1] * B + ch2[i];
reverse(ch2 + 1, ch2 + n + 1);
}
unsigned long long get_hash(int f, int l, int r) {
if(f == 1) {
// cout << l << " " << r << " " << ch1[l] << "!!!\n";
return h1[r] - h1[l - 1] * pow_B[r - l + 1];
}
if(f == 2) {
// cout << l << " " << r << " " << ch2[l] << "!!!!\n";
l = n - l + 1, r = n - r + 1;
return h2[l] - h2[r - 1] * pow_B[l - r + 1];
}
}
void Work() {
for(int i = 1;i <= n; i++) {
int len = r_[i * 2 + 1] - 1;
int L = i - len / 2 - 1, R = i + len / 2 + 1;
int l = len / 2 + 1, r = min(i - 1, n - i), mid, res = 0;
while(l <= r) {
mid = (l + r) >> 1;
// if(i == 4) cout << l << " " << r << "\n";
if(get_hash(2, i - mid, L) == get_hash(1, R, i + mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
ans = max(ans, res * 2 + 1);
len = r_[i * 2] - 1;
L = i - len / 2 + 1, R = i + len / 2;
l = len / 2 + 1, r = min(i, n - i), mid, res = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(get_hash(2, i - mid + 1, L) == get_hash(1, R, i + mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
ans = max(ans, res * 2);
// cout << i << ":" << ans << "\n";
}
}
int main() {
// freopen("str.in","r",stdin); freopen("str.out","w",stdout);
scanf("%d", &n);
pow_B[0] = 1;
for(int i = 1;i <= n; i++) pow_B[i] = pow_B[i - 1] * B;
cin >> (ch1 + 1);
ch2[1] = ch1[1]; ch2[n] = ch1[n];
for(int i = 2;i <= n - 1; i++) cin >> ch2[i];
// cout << (ch2 + 1) << "\n";
Hash();
Manacher(1); Work();
Manacher(2); Work();
// cout << (ch1 + 1) << "\n";
// for(int i = 1;i <= n; i++) cout << i << ":" << r_[i * 2 + 1] << "\n";
printf("%d", ans);
fclose(stdin); fclose(stdout);
return 0;
}
/*
6
ABAECB
B
C
D
E
10
AAAAAAAAAA
A
B
C
D
E
F
G
H
*/
T3
称一个的无向图是好的，满足:
- 任意一个子连通图的点数都相等，且都为完全图。
我们将所有\(n\)个点的好无向图拿出来，产生一个集合，每个好无向图是一个元素。
现在有\(m\)种颜色，求染色方案数，模\(999999599\)。
两种方案数不同当且仅当存在一个元素的颜色不同。
\(n <= 1e9, m <= 1e9\)
如果说这个集合的大小为\(k\), 那么最后答案就是\(k^m\), 直接快速幂就好了.
主要是怎么求\(k\), 首先我们可以列出这个式子:
\[k = \displaystyle \sum_{d \mid n} \frac{C_{n}^d*C_{n-d}^d\dots C_{d}^{d}}{\frac{n}{d}!} \] 意思就就是从把这\(n\)个点分成\(\frac{n}{d}\)份, 每份选\(d\)个的不同方案数.
化简一下 :
\[k = \displaystyle \sum_{d \mid n} \frac{n!}{d!^{\frac{n}{d}}\frac{n}{d}!} \] 然后求就好了, 注意到\(n <= 1e9\), 所以它的约数要\(dfs\)搜出来.
还注意到\(P-1\)不是质数, 所以我们还需要用CRT做. 注意算阶乘模一个数P的时候, 需要像扩展Lucas一样, 否则分母就会出现0.
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e6, mod = 999999599;
int n, m, cnt;
int prime[N], is_prime[N];
int ksm(int x, int y, int modp) {
int res = 1;
while(y) { if(y & 1) res = 1ll * res * x % modp; x = 1ll * x * x % modp; y >>= 1; }
return res;
}
int inv(int x, int modp) {
return ksm(x, modp - 2, modp);
}
void make_prime() {
for(int i = 2;i < N; i++) {
if(!is_prime[i]) prime[++ cnt] = i;
for(int j = 1;j <= cnt && i * prime[j] < N; j++) {
is_prime[i * prime[j]] = 1;
if(!(i % prime[j])) break ;
}
}
}
const int mod_1 = 999999598;
int tot, ANS;
int p[N], c[N], a[6], M[6], t[6], P[6] = {2, 13, 5281, 7283};
int calc_t(int x, int p_) {
int res = 0, base = p_;
while(x >= p_) res += x / p_, p_ *= base;
return res;
}
int calc_q(int n_, int modp) {
if(n_ <= 1) return 1;
// cout << n_ << "\n";
int res = calc_q(n_ / modp, modp), H = 1;
for(int i = 1;i < modp; i++) H = 1ll * H * i % modp;
H = ksm(H, n_ / modp, modp);
res = 1ll * res * H % mod;
for(int i = n_ / modp * modp + 1;i <= n_; i++) res = 1ll * res * i % modp;
return res;
}
int CRT() {
int res = 0;
for(int i = 0;i < 4; i++) M[i] = mod_1 / P[i], t[i] = ksm(M[i], P[i] - 2, P[i]);
for(int i = 0;i < 4; i++) res = (res + 1ll * a[i] * M[i] % mod_1 * t[i] % mod_1) % mod_1;
return res;
}
int calc(int d) {
// cout << d << "---------->\n";
int n_d = n / d;
for(int i = 0;i < 4; i++) {
int A = calc_t(n, P[i]), B = calc_t(d, P[i]), C = calc_t(n_d, P[i]);
if(A - C - B * n_d > 0) a[i] = 0;
else a[i] = 1ll * calc_q(n, P[i]) * inv(ksm(calc_q(d, P[i]), n_d, P[i]), P[i]) % P[i] * inv(calc_q(n_d, P[i]), P[i]) % P[i];
// cout << i << "!!!!!!\n";
}
// cout << CRT() << "\n";
return CRT();
}
void dfs(int now, int number) {
// cout << now << "!!!\n";
if(now == tot + 1) { ANS += calc(number); return ; }
int res = 1;
for(int i = 0;i <= c[now]; i++) {
dfs(now + 1, number * res); res *= p[now];
}
}
void div(int n_) {
tot = 0;
memset(c, 0, sizeof(c));
int tmp = n_;
for(int i = 1;i <= cnt && prime[i] <= tmp; i++)
if(!(tmp % prime[i])) {
p[++ tot] = prime[i];
while(!(tmp % prime[i])) c[tot] ++, tmp /= prime[i];
}
if(tmp > 1) p[++ tot] = tmp, c[tot] = 1;
// for(int i = 1;i <= tot; i++) cout << p[i] << " " << c[i] << "!!!!!!-----\n";
dfs(1, 1);
}
signed main() {
freopen("count.in","r",stdin); freopen("count.out","w",stdout);
make_prime();
for(int T = read(); T ; T --) {
n = read(); m = read(); ANS = 0;
div(n);
// cout << ANS << "+++\n";
printf("%d\n", ksm(m, ANS, mod));
}
fclose(stdin); fclose(stdout);
return 0;
}
/*
2
4 1
4 2
1
999999 99999999
*/