20220901
SP30919 GCDS - Sabbir and gcd problem
思路：显然答案就是不是任意一个数的因数的最小的质数。这个可以在线性筛的时候记录每个数的最小的素因数即可。
算法：线性筛。
技巧：线性筛可以筛每个数的最小的素因数。
想到了的：都想到了。
没想到的：无。
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5, W = 1e7;
int n, a[N + 10];
int prm[W + 10], notPrm[W + 10], totp, b[W + 10], notOk[W + 10];
void sieve() {
for (int i = 2; i <= W; i++) {
if (!notPrm[i]) prm[++totp] = i, b[i] = i;
for (int j = 1; j <= totp && i * prm[j] <= W; j++) {
notPrm[i * prm[j]] = 1;
b[i * prm[j]] = prm[j];
if (i % prm[j] == 0) break;
}
}
}
void mian() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
for (int j = a[i]; j > 1; j /= b[j]) notOk[b[j]] = 1;
}
for (int i = 1; i <= totp; i++)
if (!notOk[prm[i]]) return printf("%d\n", prm[i]), void();
}
int main() {
sieve();
int T; scanf("%d", &T);
while (T--) { memset(notOk, 0, sizeof(notOk)); mian(); }
return 0;
}
20220905
CF1061C Multiplicity
思路：设 \(f_{i,j}\) 为考虑前 \(i\) 个数，子序列长度为 \(j\) 的方案数，则：
\[f_{i,j}=\begin{cases}f_{i-1,j},&j\nmid a_i\\f_{i-1,j-1}+f_{i-1,j},&j\mid a_i\end{cases} \]第一维可以压掉。然后我们发现真正要被转移到的地方很少，于是时间复杂度也 OK 了。
算法：dp。
技巧：只考虑有用状态。
想到了的：都想到了。
没想到的：无。
代码
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <vector>
using namespace std;
const int N = 1e5, P = 1e9 + 7;
int n, a[N + 10], f[N + 10];
vector<int> d[N + 10];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
for (int j = 1; j <= int(sqrt(a[i])); j++)
if (a[i] % j == 0) {
d[i].push_back(j);
if (j * j != a[i]) d[i].push_back(a[i] / j);
}
sort(d[i].begin(), d[i].end(), greater<int>());
}
f[0] = 1;
for (int i = 1; i <= n; i++)
for (auto j : d[i])
if (j <= n) (f[j] += f[j - 1]) %= P;
int ans = 0;
for (int i = 1; i <= n; i++)
(ans += f[i]) %= P;
printf("%d\n", ans);
return 0;
}
P2606 [ZJOI2010]排列计数
思路：把不等关系画成一棵树（根为 \(1\)）然后 dp。设 \(f_u\) 表示以 \(u\) 为根的子树的答案，则：
\[f_u=f_{2u}f_{2u+1}{siz_{2u}+siz_{2u+1}\choose siz_{2u}} \]注意模数可以很小，所以求组合数要用 Lucas 定理。
算法：树形 dp、计数、Lucas。
技巧：建立不等关系树。
想到了的：都想到了。
没想到的：无。
代码
#include <algorithm>
#include <cstdio>
#include <tuple>
using namespace std;
const int N = 1e6;
int n, P;
int fac[N + 10], ifac[N + 10];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % P;
a = 1LL * a * a % P; b >>= 1;
}
return res;
}
void init() {
int lim = min(N, P - 1);
fac[0] = 1;
for (int i = 1; i <= lim; i++)
fac[i] = 1LL * fac[i - 1] * i % P;
ifac[lim] = qpow(fac[lim], P - 2);
for (int i = lim - 1; i >= 0; i--)
ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;
}
int comb(int a, int b) {
if (a < 0 || b < 0 || a < b) return 0;
return 1LL * fac[a] * ifac[b] % P * ifac[a - b] % P;
}
int C(int a, int b) {
if (a < P && b < P) return comb(a, b);
return 1LL * C(a / P, b / P) * comb(a % P, b % P) % P;
}
pair<int, int> f(int x) {
if (x > n) return {1, 0};
int la, ls, ra, rs;
tie(la, ls) = f(x * 2);
tie(ra, rs) = f(x * 2 + 1);
return {1LL * la * C(ls + rs, ls) % P * ra % P, ls + rs + 1};
}
int main() {
scanf("%d%d", &n, &P);
init();
printf("%d\n", f(1));
return 0;
}
CF245H Queries for Number of Palindromes
思路：先用一遍 dp 求出每个子串是不是回文的，然后求一遍这个 dp 数组的二维前缀和。
算法：dp、前缀和。
技巧：回文串问题可以区间 dp。
想到了的：都想到了。
没想到的：无。
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5000;
int n, m;
char s[N + 10];
bool f[N + 10][N + 10];
int g[N + 10][N + 10];
int main() {
scanf("%s", s + 1);
n = int(strlen(s + 1));
for (int i = 1; i <= n; i++) {
f[i][i] = 1;
if (i < n) f[i][i + 1] = s[i] == s[i + 1];
}
for (int len = 3; len <= n; len++)
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
f[l][r] = s[l] == s[r] && f[l + 1][r - 1];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + f[i][j];
scanf("%d", &m);
while (m--) {
int l, r; scanf("%d%d", &l, &r);
printf("%d\n", g[r][r] - g[l - 1][r] - g[r][l - 1] + g[l - 1][l - 1]);
}
return 0;
}