T1摆棋子
看到这么多的限制，第一直觉就是网络流，最小费用最大流不能做，因为把棋子代价看成1后最大流的条件并不好满足。
注意到每一行每一列都有一个最小限制，对应到网络流上就是流的下界，整体跑一个有下界的最小流就可以了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define DB double
using namespace std;
int n, m, k, x, y, tot = 1, S, T, SS, TT, ans, flow;
const int N = 105, inf = 1 << 30;
int X[N], Y[N], vis[N][N], d[N * N], A[N * N];
int head[N * N];
struct bian
{
int to, nt, cap;
} e[N * N * 4];
void add(int f, int t, int c)
{
e[++tot] = (bian) {t, head[f], c};
head[f] = tot;
}
void ADD(int f, int t, int c)
{
add(f, t, c); add(t, f, 0);
}
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
queue<int>q;
int bfs(int S, int T)
{
int x;
memset(d, 0, sizeof(d));
while (!q.empty())q.pop();
q.push(S); d[S] = 1;
while (!q.empty())
{
x = q.front(); q.pop();
for (int i = head[x]; i; i = e[i].nt)
if (e[i].cap && !d[e[i].to])
{
d[e[i].to] = d[x] + 1;
q.push(e[i].to);
if (e[i].to == T)return 1;
}
}
return 0;
}
int dinic(int x, int flow, int T)
{
if (x == T || !flow)return flow;
int res = flow, k;
for (int i = head[x]; i; i = e[i].nt)
if (e[i].cap && d[e[i].to] == d[x] + 1)
{
k = dinic(e[i].to, min(e[i].cap, res), T);
if (!k)d[e[i].to] = 0;
e[i].cap -= k; e[i ^ 1].cap += k;
res -= k;
}
return flow - res;
}
bool pan()
{
int js;
for (int i = 1; i <= n; ++i)
{
js = 0;
for (int j = 1; j <= m; ++j)
if (!vis[i][j])++js;
if (js < X[i])return 1;
}
for (int j = 1; j <= m; ++j)
{
js = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i][j])++js;
if (js < Y[j])return 1;
}
return 0;
}
int main()
{
freopen("chessman.in", "r", stdin);
freopen("chessman.out", "w", stdout);
cin >> n >> m >> k; S = n + m + 1, T = n + m + 2, SS = n + m + 3, TT = n + m + 4;
for (int i = 1; i <= n; ++i)X[i] = read();
for (int i = 1; i <= m; ++i)Y[i] = read();
for (int i = 1; i <= k; ++i)
{
x = read(); y = read();
vis[x][y] = 1;
}
if (pan())
{
puts("No Solution");
fclose(stdin); fclose(stdout);
return 0;
}
for (int i = 1; i <= n; ++i)
{
ADD(S, i, inf - X[i]);
A[S] -= X[i]; A[i] += X[i];
}
for (int i = 1; i <= m; ++i)
{
ADD(n + i, T, inf - Y[i]);
A[n + i] -= Y[i]; A[T] += Y[i];
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (!vis[i][j])ADD(i, n + j, 1);
for (int i = 1; i <= n + m + 2; ++i)
if (A[i] > 0) {ADD(SS, i, A[i]);}
else if (A[i])ADD(i, TT, -A[i]);
while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
ADD(T, S, inf);
while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
cout << e[tot].cap;
fclose(stdin); fclose(stdout);
return 0;
}
T2旅行路线
把度数看成一个字符，就变成了树上的不同子串个数问题。
一个序列的我们能解决，放到树上只需要把last改成fa的id就行了。
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#define LL long long
#define DB double
using namespace std;
int n, tot, x, y, cnt;
const int N = 1000010;
int head[N], du[N], id[N], len[N], fa[N];
map<int, int>tr[N];
struct bian {int to, nt;} e[N];
LL ans;
void add(int f, int t)
{
e[++tot] = (bian) {t, head[f]};
head[f] = tot;
}
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
void Insert(int x, int Q, int las)
{
int np = ++cnt, p = las, q, nq;
len[np] = len[p] + 1; id[Q] = cnt;
for (; p && tr[p].find(x) == tr[p].end(); p = fa[p])tr[p][x] = np;
if (!p)fa[np] = 1;
else if (len[q = tr[p][x]] == len[p] + 1)fa[np] = q;
else
{
len[nq = ++cnt] = len[p] + 1;
fa[nq] = fa[q]; fa[q] = fa[np] = nq; tr[nq] = tr[q];
for (; p; p = fa[p])
{
if (tr[p].find(x) == tr[p].end() || tr[p][x] != q)break;
tr[p][x] = nq;
}
}
}
void dfs(int x, int fa)
{
Insert(du[x], x, id[fa]);
for (int i = head[x]; i; i = e[i].nt)
if (e[i].to != fa)dfs(e[i].to, x);
}
int main()
{
freopen("route.in", "r", stdin);
freopen("route.out", "w", stdout);
cnt = id[0] = 1; cin >> n;
for (int i = 1; i < n; ++i)
{
x = read(); y = read();
add(y, x); du[x]++; du[y]++;
}
dfs(1, 0);
for (int i = 2; i <= cnt; ++i)ans += len[i] - len[fa[i]];
cout << ans;
fclose(stdin); fclose(stdout);
return 0;
}
T3流浪者
总的方案数就是(C_{n+m-2}^{n-1}),因为体力减小的快，只有log种取值，所以总的体力是对每一种s乘上相应的方案数的和。
f[i][j] 表示从起点出发经过恰好 j 个特殊点到达第 i 个障碍点的方案,依然考虑容斥，枚举不合法路径上除 i 之外的第 j 个特殊点
(displaystyle f[i][j]=C_{x_i+y_i}^{x_i} - sum_{k=1}^{i-1}f[k][j]·ways(k, i) - sum_{k=1}^{j-1}f[i][k])
ways(i, j) 表示从第 i 个特殊点到第 j 个障碍点的方案
不懂的话可以吧右边的减号移到左边来。
#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
#define LL long long
#define DB double
using namespace std;
int n, m, k, s, x, y, mx;
const int mod = 1e9 + 7, N = 200010, M = 2005;
int ex[M];
LL jc[N], inv[N], f[M][M], w[M][M], sum[M][M];
LL ans;
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
struct dian
{
int x, y;
friend bool operator <(const dian &a, const dian &b) {return a.x + a.y < b.x + b.y;}
} p[M];
LL ksm(LL a, LL b, LL mod)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)res = res * a % mod;
return res;
}
void YYCH()
{
jc[0] = jc[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= n + m; ++i)jc[i] = jc[i - 1] * i % mod;
inv[n + m] = ksm(jc[n + m], mod - 2, mod);
for (int i = n + m - 1; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL C(LL n, LL m)
{
if (n < m || n < 0 || m < 0)return 0;
return jc[n] * inv[m] % mod * inv[n - m] % mod;
}
inline LL ni(LL x) {return ksm(x, mod - 2, mod);}
signed main()
{
freopen("rover.in", "r", stdin);
freopen("rover.out", "w", stdout);
cin >> n >> m >> k >> s;
YYCH();
for (int i = 1; i <= k; ++i)
p[i].x = read(), p[i].y = read();
p[0] = (dian) {1, 1}; p[++k] = (dian) {n, m};
sort(p, p + k + 1); ex[0] = s;
for (int i = 1; i <= 20; ++i)
{
ex[i] = (ex[i - 1] + 1) >> 1;
if (ex[i] == 1 && !mx)mx = i;
}
f[0][0] = 1;
for (int i = 0; i <= k; ++i)
for (int j = 0; j < i; ++j)
w[i][j] = C(p[i].x - p[j].x + p[i].y - p[j].y, p[i].x - p[j].x);
for (int i = 1; i <= k; ++i)
for (int j = 0; j <= mx + 1; ++j)
{
f[i][j] = C(p[i].x + p[i].y - 2, p[i].x - 1);
if (j)f[i][j] = (f[i][j] - sum[i][j - 1] + mod) % mod;
for (int l = 0; l < i; ++l)
f[i][j] = (f[i][j] - f[l][j] * w[i][l] % mod + mod) % mod;
if (j)sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;
else sum[i][j] = f[i][j];
}
for (int i = 1; i <= mx; ++i)
(ans += f[k][i] * ni(C(n + m - 2, n - 1)) % mod * ex[i - 1] % mod) %= mod;
ans = (ans + (C(n + m - 2, n - 1) - sum[k][mx] + mod) % mod * ni(C(n + m - 2, n - 1)) % mod) % mod;
cout << ans;
fclose(stdin); fclose(stdout);
return 0;
}