T1
Topcoder SRM 565 div1 Medium - TheDivisionGame
博弈论。一个数字的 SG 函数值即为其质因子个数，可以用数学归纳法证明。接下来我们用 \(\sqrt{10^9}\) 以内的质数去除区间内的每个数求出区间内每个数的质因子个数。别忘了一个数还可能有大于根号的质因子。然后根据 SG 函数的结论，先手必胜当且仅当区间内每个数的 SG 函数值异或起来是 \(0\)。所以只需要求有多少区间异或和为 \(0\)。做个异或前缀和随便搞。
代码
#include <iostream>
#include <map>
using namespace std;
int p[300005], pcnt;
bool vis[300005];
void F(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i])
p[++pcnt] = i;
for (int j = 1; j <= pcnt && 1ll * p[j] * i <= n; j++) {
vis[p[j] * i] = 1;
if (i % p[j] == 0)
break;
}
}
}
int cnt[100];
int a[1000005];
int v[1000005];
int main() {
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
int l, r;
cin >> l >> r;
for (int i = 1; i <= r - l + 1; i++) v[i] = i + l - 1;
F(35000);
for (int i = 1; i <= pcnt; i++) {
for (long long j = ((l - 1) / p[i] + 1ll) * p[i]; j <= r; j += p[i])
while (v[j - l + 1] % p[i] == 0) v[j - l + 1] /= p[i], a[j - l + 1]++;
}
long long ans = 0;
cnt[0]++;
for (int i = 1; i <= r - l + 1; i++) {
a[i] += (v[i] != 1);
a[i] ^= a[i - 1];
ans += cnt[a[i]];
cnt[a[i]]++;
}
cout << (1ll * r - l + 2) * (1ll * r - l + 1) / 2 - ans << "\n";
return 0;
}
T2
Topcoder SRM 566 div1 Medium - PenguinEmperor
步数太多没意义，反正都要对 \(n\) 取模。所以先算出步数循环的轮数，然后算出剩下多少步，做矩乘优化 dp。由于矩阵都是循环矩阵，所以矩乘可以写到 \(n^2\)。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
struct Loop_Matrix {
int a[355];
Loop_Matrix() { memset(a, 0, sizeof a); }
int& operator[](int x) { return a[x]; }
} T[355];
int n, m;
Loop_Matrix operator*(Loop_Matrix a, Loop_Matrix b) {
Loop_Matrix c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
c[i] += a[j] * b[(i - j + n) % n] % P;
c[i] %= P;
}
return c;
}
Loop_Matrix qpow(Loop_Matrix x, int y) {
Loop_Matrix ret;
ret[0] = 1;
while (y) {
if (y & 1)
ret = ret * x;
y >>= 1;
x = x * x;
}
return ret;
}
signed main() {
// freopen("B.in", "r", stdin);
// freopen("B.out", "w", stdout);
cin >> n >> m;
T[n][0] = 1;
for (int i = 0; i < n; i++) {
T[i][i] = T[i][(n - i) % n] = 1;
T[n] = T[n] * T[i];
}
int x = (m + 1) / n;
T[n] = qpow(T[n], x);
for (int i = 0; i < (m + 1) % n; i++) T[n] = T[n] * T[i];
cout << T[n][0] << "\n";
return 0;
}
T3
Topcoder SRM 576 div1 Medium - TheExperiment
首先观察每个盆能接到的都是些什么东西。发现每个盆一定接到一个区间，而且如果按照盆之间的相邻和覆盖关系连边，则每个连通块中都至少存在一个长度为 \(L\) 的区间。那么考虑 \(dp[i][j][0 / 1 / 2]\) 表示前 \(i\) 个数，选出了 \(j\) 个区间，最后一维的 \(0\) 代表最后一个数不被任何区间选中，\(1\) 代表最后一个数所在连通块暂时还没有长度为 \(L\) 的区间，\(2\) 表示已经有了长度为 \(L\) 的区间。然后由于数据范围很小，所以转移就暴力枚举就好了。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 1000000009;
int dp[305][305][3];
int n, m, l, L, R;
string str;
int a[305];
signed main() {
// freopen("C.in", "r", stdin);
// freopen("C.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
str += s;
}
n = str.size();
for (int i = 0; i < n; i++) a[i + 1] = str[i] - '0' + a[i];
cin >> m >> l >> L >> R;
for (int i = 0; i <= n; i++) dp[0][i][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k < j; k++) dp[i][j][0] = (dp[i][j][0] + dp[i][k][2]) % P;
for (int k = max(0ll, j - l); k < j; k++) {
if (L <= a[j] - a[k] && a[j] - a[k] <= R) {
if (k == j - l)
dp[i][j][2] = (dp[i][j][2] + dp[i - 1][k][0] + dp[i - 1][k][1] + dp[i - 1][k][2]) % P;
else {
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][k][0] + dp[i - 1][k][1]) % P;
dp[i][j][2] = (dp[i][j][2] + dp[i - 1][k][2]) % P;
}
}
}
}
}
cout << (dp[m][n][0] + dp[m][n][2]) % P << "\n";
return 0;
}
T4
Topcoder SRM 568 div1 Medium - EqualSums
可以证明条件 \(2\) 与所有 \(a_{i, j}\) 均能表示成 \(b_i + c_j\) 等价。所以对于每个限制的位置，实际上是限制这一行的 \(b_i\) 和这一列的 \(c_j\) 的和。将限制作为边建图，发现一个连通块中确定一个点则其他所有点都能确定，而连通块之间是相互独立的。条件 \(1\) 就是要求所有 \(b_i, c_i \le 0\)。发现把所有 \(b_i\) 加一个数，而 \(c_i\) 减去这个数仍合法，但是构造出的 \(a\) 却是相同的。所以我们只计算 \(\min \{ b_i \} = 0\) 的解。我们对于每一个连通块枚举其中一个数填什么，算它有多少种填法，然后把所有连通块的填法乘起来即可。要求 \(\min \{ b_i \} = 0\) 就容斥一下。拿所有情况减去不合要求的即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 1000000007;
int n;
int s[55][55];
int lab;
bool flag = 1;
int sz;
int stk[55555];
int a[10005];
bool vis[100005];
int head[100005], nxt[200005], to[200005], ew[200005], ecnt;
void add(int u, int v, int ww) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, ew[ecnt] = ww; }
void dfs(int x, int y = 0) {
vis[x] = 1;
stk[++sz] = x;
if (y == 0)
flag &= (a[x] >= 0);
else
flag &= ((x <= n && a[x] > 0) || (x > n && a[x] >= 0));
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v])
flag &= (a[v] == ew[i] - a[x]);
else {
a[v] = ew[i] - a[x];
dfs(v, y);
}
}
}
signed main() {
// freopen("D.in", "r", stdin);
// freopen("D.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
for (int j = 0; j < n; j++) {
if (str[j] == '-')
s[i][j + 1] = -1;
else
s[i][j + 1] = (str[j] - '0');
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i][j] != -1) {
add(i, j + n, s[i][j]);
add(j + n, i, s[i][j]);
}
}
}
int a1 = 1, a2 = 1;
for (int i = 1; i <= n * 2; i++) {
if (!vis[i]) {
int c1 = 0, c2 = 0;
for (int j = 0; j <= 9; j++) {
sz = 0;
a[i] = j;
flag = 1;
dfs(i);
c1 += flag;
for (int k = 1; k <= sz; k++) vis[stk[k]] = 0;
}
for (int j = 0; j <= 9; j++) {
sz = 0;
a[i] = j;
flag = 1;
dfs(i, 1);
c2 += flag;
for (int k = 1; k <= sz; k++) vis[stk[k]] = 0;
}
for (int k = 1; k <= sz; k++) vis[stk[k]] = 1;
a1 = (a1 * c1) % P, a2 = (a2 * c2) % P;
}
}
cout << (a1 - a2 + P) % P;
return 0;
}
T5
Topcoder SRM 599 div1 Hard - SimilarNames
首先按照前缀关系建树，则限制转化为给点标号，要求某些编号的点必须是某些编号点的祖先。进行类似于树上背包的 dp，枚举子集转移。注意到有很多集合本身就不满足限制，比如说只出现了某个应该是祖先的点，而对应的后继点却没有出现。这些集合直接扔掉不枚举，就能过了。
代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int P = 1000000007;
int n, m;
bool isp[55][55];
string str[55];
int a[10], b[10];
int S;
int head[55], nxt[105], to[105], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int dp[55][100003];
int r[100003], s[100003];
int lst[55][100003], cur[55][100003];
int cnt = -1;
vector<int> vec;
void dfs(int x) {
cur[x][0] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
for (int j = 0; j <= S; j++) lst[x][j] = cur[x][j];
dfs(v);
for (auto j : vec) {
for (int k = j; k; k = (k - 1) & j) {
if ((r[k] & (j ^ k)) == 0 && dp[v][k])
cur[x][j] = (cur[x][j] + 1ll * lst[x][j ^ k] * dp[v][k]) % P;
}
}
}
for (int i = 0; i <= S; i++) dp[x][i] = cur[x][i];
if (x) {
for (int i = 0; i <= S; i++) {
for (int j = 0; j <= cnt; j++) {
if ((i & (1 << j)) && (s[i ^ (1 << j)] & (1 << j)) == 0)
dp[x][i] = (dp[x][i] + 1ll * cur[x][i ^ (1 << j)]) % P;
}
}
}
}
int id[105];
int fa[105];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("E.in", "r", stdin);
// freopen("E.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> str[i];
sort(str + 1, str + n + 1, [](string a, string b) { return a.size() < b.size(); });
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (str[i] == str[j].substr(0, str[i].size()))
fa[j] = i;
}
}
for (int i = 1; i <= n; i++) add(fa[i], i);
cin >> m;
for (int i = 1; i <= m; i++) cin >> a[i], id[a[i]] = 1;
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i], id[b[i]] = 1;
for (int i = 0; i < n; i++) {
if (id[i] == 1)
id[i] = ++cnt;
}
for (int i = 1; i <= m; i++) {
a[i] = id[a[i]], b[i] = id[b[i]];
r[1 << a[i]] |= (1 << b[i]);
r[1 << b[i]] |= (1 << a[i]);
s[1 << a[i]] |= (1 << b[i]);
}
S = (1 << (cnt + 1)) - 1;
for (int i = 0; i <= S; i++) {
bool flag = 0;
for (int j = 1; j <= m; j++)
flag |= ((i & (1 << a[j])) && !(i & (1 << b[j])));
if (!flag)
vec.emplace_back(i);
}
for (int i = 0; i <= S; i++) {
for (int j = 0; j <= cnt; j++) {
if (i & (1 << j)) {
r[i] |= r[1 << j];
s[i] |= s[1 << j];
}
}
}
dfs(0);
int ans = dp[0][S];
for (int i = 1; i <= (n - cnt - 1); i++) ans = 1ll * ans * i % P;
cout << ans << "\n";
return 0;
}
组合博弈游戏的 SG 函数是所有子游戏的异或和。用质数去扫区间内的每个数来分解质因子 / 求质因子个数。
循环矩乘的写法。
别瞎写转移。
条件限制的转化。
按照字符串的前缀关系建树。对不合法状态的不枚举。
标签：Matrix,int,55,++,str,20240326,Loop From： https://www.cnblogs.com/forgotmyhandle/p/18097549