T1
Topcoder SRM 632 div2 Hard - GoodSubset
直接记搜，不整除就不取当前数。由于给定数的因数个数是很少的，所以记搜完全跑得过去。
代码
#include <iostream>
#include <map>
using namespace std;
const int P = 1000000007;
map<pair<int, int>, int> vis;
int n;
int a[105];
int V;
void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int dfs(int p, int v) {
if (p == n + 1)
return v == 1;
pair<int, int> pr = make_pair(p, v);
if (vis.count(pr))
return vis[pr];
int ret = 0;
if (v % a[p] == 0)
ret = dfs(p + 1, v / a[p]);
Madd(ret, dfs(p + 1, v));
return vis[pr] = ret;
}
int main() {
cin >> V >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << dfs(1, V) - (V == 1) << "\n";
return 0;
}
T2
NFLSOJ P2845 数位和同余
考虑类似于根号分治的东西。对于 \(P\) 比较小的情况，直接数位 dp，记录前面位的数位和和原数对 \(P\) 的余数。我写的可以跑到 \(P = 10^4\)。对于剩下的情况，首先注意到数位和不大，在 \([0, 90]\)，所以余数也只能是这些。我们枚举数位和，每次给当前数加上 \(P\) 直到超过 \(M\) 为止，检查每个数对 \(P\) 取模是否等于其数位和。复杂度 \(O(能过)\)。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
int P, M;
int dp[15][95][10005];
int d[15], dcnt;
int dfs(int pos, int x, int y, bool lim) {
if (pos == 0)
return x == y;
if (!lim && dp[pos][x][y] != -1)
return dp[pos][x][y];
int ret = 0;
int up = (lim ? d[pos] : 9);
for (int i = 0; i <= up; i++)
ret += dfs(pos - 1, (x + i) % P, (y * 10 + i) % P, lim & (i == up));
if (!lim)
dp[pos][x][y] = ret;
return ret;
}
int calc(int x) {
int ret = 0;
while (x) ret += x % 10, x /= 10;
return ret;
}
signed main() {
memset(dp, -1, sizeof dp);
cin >> P >> M;
int tmp = M;
while (M) d[++dcnt] = M % 10, M /= 10;
if (P <= 10000)
cout << dfs(dcnt, 0, 0, 1) - 1 << "\n";
else {
int a1 = -1;
for (int i = 0; i <= dcnt * 9; i++) {
for (int j = i; j <= tmp; j += P)
a1 += (i == calc(j) % P);
}
cout << a1 << "\n";
}
return 0;
}
T3
Topcoder SRM 555 div1 Medium - XorBoard
先把所有操作中对同一行 / 列的两次操作的去掉，设有 \(x\) 个行在最后被操作了，\(y\) 个列在最后被操作了。可以列出白色格子数量 \(S = xW + yH - 2xy\)。枚举 \(x\)，可以解出 \(y\)，然后对解出的 \(y\) 有一些合法性的要求。特别地，可能会解出无穷多解的情况，这是合法的。确定了行列各有多少在最后是被操作的，就可以计算方案数。先把这些行列操作掉，则还要求行和列的剩余操作次数都是 \(2\) 的倍数。相当于把 \(x\) 个被操作的行分配到 \(H\) 个行里，把剩下的很多对操作分配到每一行上。两部分都是组合数，把行和列的方案乘起来最后求和即为答案。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 555555555;
int H, W, r, c, S;
int C[4005][4005];
void Madd(int& x, int y) { (x += y % P) >= P ? (x -= P) : 0; }
signed main() {
cin >> H >> W >> r >> c >> S;
C[0][0] = 1;
for (int i = 1; i <= 4000; i++) {
for (int j = 0; j <= 4000; j++)
j == 0 ? (C[i][j] = 1) : (C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P);
}
int ans = 0;
for (int x = 0; x <= H; x++) {
int p = S - x * W;
int q = H - 2 * x;
if (q != 0 && p % q != 0)
continue;
else if (q == 0 && p != 0)
continue;
if (p == 0 && q == 0) {
for (int y = 0; y <= W; y++) {
if ((r - x < 0 || ((r - x) & 1)) || (c - y < 0 || ((c - y) & 1)))
continue;
int n1 = (r - x) >> 1;
int n2 = (c - y) >> 1;
Madd(ans, (C[H][x] * C[W][y] % P) * (C[n1 + H - 1][H - 1] * C[n2 + W - 1][W - 1] % P));
}
} else {
int y = p / q;
if (y < 0 || y > W)
continue;
if ((r - x < 0 || ((r - x) & 1)) || (c - y < 0 || ((c - y) & 1)))
continue;
int n1 = (r - x) >> 1;
int n2 = (c - y) >> 1;
Madd(ans, (C[H][x] * C[W][y] % P) * (C[n1 + H - 1][H - 1] * C[n2 + W - 1][W - 1] % P));
}
}
cout << ans << "\n";
return 0;
}
T4
Topcoder SRM 550 div1 Hard - ConversionMachine
考虑所有合法操作一定规约成先把原串变成合法，然后三个一组地对某个字母操作。考虑一个 \(dp[a][i][j][k]\) 表示操作 \(a\) 次后有 \(i\) 个字母剩 \(1\) 次操作正确，\(j\) 个剩 \(2\) 次，\(k\) 个已经正确的方案数。转移考虑改哪种字符。由于 \(i + j + k = n\)，最后一维可以去掉。注意到这里没有限制操作代价，是因为对代价的限制可以转化为对操作次数的限制。根据前面的规约，我们可以算出合法的最小代价。然后三个一组的操作相当于每次给代价加上特定值。当代价超过限制时就不能操作了。所以对代价的限制本质上相当于对操作次数的限制。所以可以直接矩乘快速幂优化这个 dp。注意这个矩乘中还有一维要记录前缀和。
代码
#include <iostream>
#include <string.h>
#include <map>
#define int long long
using namespace std;
const int P = 1000000007;
const int N = 100;
struct Matrix {
int a[105][105];
int* operator[](int x) { return a[x]; }
Matrix(int x = 0) {
memset(a, 0, sizeof a);
for (int i = 0; i <= N; i++) a[i][i] = x;
}
} I, T;
Matrix operator*(Matrix a, Matrix b) {
Matrix c;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
for (int k = 0; k <= N; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j] % P) % P;
}
}
return c;
}
Matrix operator^(Matrix x, int y) {
Matrix ret(1);
while (y) {
if (y & 1)
ret = ret * x;
y >>= 1;
x = x * x;
}
return ret;
}
map<pair<int, int>, int> mp;
int f(int a, int b) { return mp[make_pair(a, b)]; }
int c[3], mxc, n;
signed main() {
string a, b;
cin >> a >> b;
n = a.size();
cin >> mxc;
cin >> c[0] >> c[1] >> c[2] >> mxc;
int Cost0 = 0, c1, c2;
c1 = c2 = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 'a' && b[i] == 'b')
Cost0 += c[0], ++c1;
if (a[i] == 'a' && b[i] == 'c')
Cost0 += c[0] + c[1], ++c2;
if (a[i] == 'b' && b[i] == 'a')
Cost0 += c[1] + c[2], ++c2;
if (a[i] == 'b' && b[i] == 'c')
Cost0 += c[1], ++c1;
if (a[i] == 'c' && b[i] == 'a')
Cost0 += c[2], ++c1;
if (a[i] == 'c' && b[i] == 'b')
Cost0 += c[2] + c[0], ++c2;
}
int S = c[0] + c[1] + c[2];
if (mxc < Cost0) {
cout << 0 << "\n";
return 0;
}
int MaxStep = (mxc - Cost0) / S;
int ncnt = 0;
for (int a1 = 0; a1 <= n; a1++) {
for (int a2 = 0; a1 + a2 <= n; a2++) {
mp[make_pair(a1, a2)] = ++ncnt;
}
}
mp[make_pair(n, 1)] = ++ncnt;
I[0][f(c1, c2)] = 1;
for (int a1 = 0; a1 <= n; a1++) {
for (int a2 = 0; a1 + a2 <= n; a2++) {
int cur = f(a1, a2);
if (a1)
T[cur][f(a1 - 1, a2)] = a1;
if (a2)
T[cur][f(a1 + 1, a2 - 1)] = a2;
if (a1 + a2 != n)
T[cur][f(a1, a2 + 1)] = n - a1 - a2;
}
}
MaxStep = MaxStep * 3 + c1 + c2 * 2 + 1;
T[f(0, 0)][f(n, 1)] = 1;
T[f(n, 1)][f(n, 1)] = 1;
I = (I * (T ^ MaxStep));
cout << I[0][f(n, 1)] << "\n";
return 0;
}
T5
Topcoder SRM 549 div1 Hard - CosmicBlocks
先枚举所有层各有哪些颜色，然后枚举相邻层间所有颜色之间的覆盖关系，然后由于要满足这个覆盖关系，我们从上往下建边，由覆盖的连向被覆盖的，然后为了限制每个颜色的数量，我们对每个颜色拆点，拆出的点间边容量为该颜色数量，所有边有流量下界 \(1\)，跑一个上下界网络流，若有解就再接一个 DAG 拓扑序计数，如果方案数合法就加入答案。
代码
#include <iostream>
#include <algorithm>
#include <time.h>
#include <random>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
int LL, RR;
struct Edge {
int u, v, l, r;
} e[1005];
int clr[10][10];
pair<int, int> es[15];
int a[10];
int in[105], out[105];
int head[1005], nxt[1005], to[1005], res[1005], ecnt;
int cur[1005];
inline void add(int u, int v, int ww) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = ww;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0;
}
int S, T;
int dep[1005];
queue<int> q;
bool bfs() {
for (int i = 1; i <= T; i++) dep[i] = -1;
dep[S] = 1;
q.push(S);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dep[v] == -1 && res[i]) {
dep[v] = dep[x] + 1;
q.push(v);
}
}
}
return (dep[T] > 0);
}
int dfs(int x, int flow) {
if (x == T)
return flow;
int ret = 0;
for (int& i = cur[x]; i; i = nxt[i]) {
int v = to[i];
if (dep[v] == dep[x] + 1 && res[i]) {
int tmp = dfs(v, min(flow, res[i]));
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
}
}
if (!ret)
dep[x] = -1;
return ret;
}
bool check(int m) {
ecnt = 1;
for (int i = 1; i <= T; i++) head[i] = 0, in[i] = out[i] = 0;
for (int i = 1; i <= m; i++) {
in[e[i].v] += e[i].l;
out[e[i].u] += e[i].l;
add(e[i].u, e[i].v, e[i].r - e[i].l);
}
S = n * 2 + 3, T = S + 1;
for (int i = 1; i <= n * 2 + 1; i++) {
if (in[i] < out[i])
add(i, T, out[i] - in[i]);
else if (in[i] > out[i])
add(S, i, in[i] - out[i]);
}
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
dfs(S, inf);
}
bool flag = 1;
for (int i = head[S]; i; i = nxt[i]) flag &= (res[i] == 0);
return flag;
}
int dp[1005];
int count(int m, int S) {
for (int i = 1; i <= n; i++) nxt[i] = 0;
for (int i = 1; i <= m; i++) nxt[es[i].first] |= (((S >> (i - 1)) & 1) << (es[i].second - 1));
for (int i = 1; i < (1 << n); i++) dp[i] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 1; j <= n; j++) {
if (((i >> (j - 1)) & 1) & ((nxt[j] & i) == nxt[j]))
dp[i] += dp[i ^ (1 << (j - 1))];
}
}
return dp[(1 << n) - 1];
}
int ans;
void get(int x, int S) {
if (S == 0) {
int e = 0;
for (int i = 1; i < x - 1; i++) {
for (int j = 1; j <= clr[i][0]; j++) {
for (int k = 1; k <= clr[i + 1][0]; k++)
es[++e] = make_pair(clr[i][j], clr[i + 1][k]);
}
}
int c = 2 * n + 1;
for (int i = 1; i <= clr[1][0]; i++) ::e[++c] = (Edge) { n << 1 | 1, clr[1][i] * 2 - 1, 0, inf };
int rec = c;
for (int i = 0; i < (1 << e); i++) {
c = rec;
for (int j = 0; j < e; j++) {
if ((i >> j) & 1)
::e[++c] = (Edge) { es[j + 1].first * 2, es[j + 1].second * 2 - 1, 1, inf };
}
if (check(c)) {
int cnt = count(e, i);
ans += (LL <= cnt && cnt <= RR);
}
}
return;
}
for (int i = S; i; i = (i - 1) & S) {
clr[x][0] = 0;
for (int j = 0; j < n; j++) {
if ((i >> j) & 1)
clr[x][++clr[x][0]] = j + 1;
}
get(x + 1, S ^ i);
}
}
int main() {
*dp = 1;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int t = clock();
int c = 0;
for (int i = 1; i <= n; i++) e[++c] = (Edge) { i << 1, n * 2 + 2, 0, inf }, e[++c] = (Edge) { i * 2 - 1, i << 1, a[i], a[i] };
e[++c] = (Edge) { n * 2 + 2, n << 1 | 1, 0, inf };
cin >> LL >> RR;
get(1, (1 << n) - 1);
cout << ans << "\n";
cerr << (clock() * 1.0 - t) / CLOCKS_PER_SEC << "\n";
return 0;
}
T6
Topcoder SRM 548 div1 Hard KingdomAndCities
先考虑 \(k = 0\) 的情况，即为 \(n\) 个点 \(m\) 条边的无向连通图计数。考虑容斥一下，数一数有多少不连通的。总共的方案数是 \(\binom{\binom{n}{2}}{m}\)，枚举根所在的连通块有几个点、几条边，有转移 \(f[n][m] = \sum_{i = 1}^{n - 1}\sum_{j = i - 1}^{\binom{i}{2}} f[i][j]\times \binom{\binom{n - i}{2}}{m - j}\)，其中 \(f[i][j]\) 是根所在连通块的方案数，后面是该连通块之外随便连的总方案数。这样就解决了 \(k = 0\) 的情况。
考虑 \(k = 1\)，相当于把一个点插到一条边中间或者并到一条边旁边形成三元环。注意，如果形成非三元环的环，则该方案可能会被与插进边的情况算重。两种分别是多了一个点一条边和一个点两条边，所以把 \(f\) 乘上各自选边的方案数加起来即为答案。
考虑 \(k = 2\)，首先考虑两个插入的点之间有边的情况。
-
此时如果把两个点共同连到一个点上形成三元环，则多了 \(2\) 个点 \(3\) 条边，方案数即为原点数。此时是否交换两个点的位置是一样的。
-
如果把两个点共同插到一条边里去，则多了 \(2\) 个点 \(2\) 条边，方案数为原边数。此时交换两个点的位置形成的方案不同，方案数要乘以 \(2\)。
-
如果把两个点并到一条边旁边，则多了 \(2\) 个点 \(3\) 条边，方案数为原边数。此时交换两个点形成的方案不同，方案数要乘以 \(2\)。
考虑插入的两个点之间没有边的情况。分别考虑两个点以什么形式插入。
-
两个点都形成三元环，多了 \(2\) 个点 \(4\) 条边，选到相同边不影响，方案数为原边数的平方。
-
一个点成三元环，一个点插入边，此时两个点不能选到相同边，理由看下面的情况。相当于多了 \(2\) 个点 \(3\) 条边，方案数为原边数 乘以 原边数减一。交换两个点的方案不同，方案数要乘以 \(2\)。
-
两个点都插入边。
-
- 插入相同边，这种情况下有一个点的边是原边，一个点的边要新开。这种情况实际上相当于前面那种情况选到了相同边，但是这种情况下交换两个点不影响，所以不能乘以 \(2\)。方案数为原边数。
-
- 插入不同边，多了 \(2\) 个点 \(2\) 条边，方案数为原边数 乘以 原边数减一。
将上面几种的方案数全加起来即为答案。
注意特判一堆奇奇怪怪的边界情况，记得开够数组。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 1000000007;
int n, m, k;
int f[3005][3005];
int C[3005][3005];
void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
signed main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
cin >> n >> k >> m;
if (m < n - 1) {
cout << 0 << "\n";
return 0;
}
C[0][0] = 1;
for (int i = 1; i <= 3000; i++) {
for (int j = 0; j <= 3000; j++)
j == 0 ? (C[i][j] = 1) : (C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P);
}
f[1][0] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= i * (i - 1) / 2; j++) {
for (int a = 1; a < i; a++) {
for (int b = a - 1; b <= j; b++)
Madd(f[i][j], f[a][b] * C[i - 1][a - 1] % P * C[C[i - a][2]][j - b] % P);
}
f[i][j] = (C[C[i][2]][j] + P - f[i][j]) % P;
}
}
if (n == 1 && m >= 1) {
cout << "0\n";
return 0;
} else if (n == 1) {
cout << (k == 0) << "\n";
return 0;
}
if (n == 2 && m > 1) {
cout << "0\n";
return 0;
} else if (n == 2) {
cout << (k == 0) << "\n";
return 0;
}
if (n == 3 && m > 3) {
cout << "0\n";
return 0;
} else if (n == 3 && m == 3) {
cout << "1\n";
return 0;
} else if (n == 3 && m == 2) {
cout << (k == 0 ? 3 : (k == 1)) << "\n";
return 0;
} else if (n == 3) {
cout << "0\n";
return 0;
}
if (k == 0)
cout << f[n][m] << "\n";
else if (k == 1)
cout << ((m - 2) * f[n - 1][m - 2] % P + (m - 1) * f[n - 1][m - 1] % P) % P << "\n";
else {
int a1 = ((n - 2) * f[n - 2][m - 3] % P + 2 * (m - 2) * f[n - 2][m - 2] % P + 2 * (m - 3) * f[n - 2][m - 3] % P) % P;
int a2 = ((m - 4) * (m - 4) * f[n - 2][m - 4] % P + 2 * (m - 3) * (m - 4) * f[n - 2][m - 3] % P
+ (m - 3) * f[n - 2][m - 3] % P + (m - 2) * (m - 3) * f[n - 2][m - 2] % P) % P;
cout << (a1 + a2) % P << "\n";
}
return 0;
}