动态规划小练2

Vexoben

Apr 14, 2019

It takes 39 minutes to read this article.

之前那篇小练写太长影响体验了，这边再开一篇。

这次的题目列表是51nod上的七级题。

（刷新以获取数学公式）

[51nod1169] 石子游戏

题意

有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。在任意多堆拿走任意多个，但至少有一堆不拿。求使得所有堆数异或和为 $0$ 的方案数。

数据范围： $n≤100，a_i≤1e9$

题解

虽然标签是 $DP$ ,但是难点似乎并不在 $DP$ 上的说……

先不考虑至少有一堆不拿的限制。

设拿过石子之后的序列为 $b$ ,枚举一个位 $k$ ，令 $k$ 是存在整数 $i$ ，使得 $a_i$ 在这一位上不等于 $b_i$ 的最高位。

显然 $a_i$ 的第 $k$ 位必须是 $1$ ，否则不满足高位限制。

那么 $DP$ 使得这一位的异或和为 $0$ ，对于不等于 $a_i$ 的数低于 $k$ 的位，我们可以在不超过高位限制下选择任意数。因为 $a_i$ 的第 $k$ 位必须是 $1$ ，这意味着它低于 $k$ 的位没有高位限制，因此一定存在一种方案使得那些低位异或起来是 $0$ 。

需要注意的是，为了不重复， $i$ 必须是第一个满足 $a_i$ 和 $b_i$ 在第 $k$ 位上不同的数。

至于至少不拿一堆，只需要减去每堆都拿的方案数。把所有数 $-1$ 再做一次就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
const int mod = 1e9 + 7;

int n, c[N];

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? z - mod : z;
}

int subset(int x, int bit) {
	if (x >= (1 << bit)) return (1 << bit);
	else return x + 1;
}

int calc(int bit, int pos) {
	int f[2] = {1, 0};
	int lim = (1LL << bit) - 1;
	int tmp = ((1LL << 31) - 1) ^ (1 << bit);

	for (int i = 1; i < pos; ++i) {
		int g[2] = {f[0], f[1]};
		f[0] = f[1] = 0;
		int now = c[i] >> bit & 1;
		upd(f[0], 1LL * g[now] * subset(c[i] & lim, bit) % mod);
		upd(f[1], 1LL * g[now ^ 1] * subset(c[i] & lim, bit) % mod);
	}
	
	for (int i = pos + 1; i <= n; ++i) {
		int g[2] = {f[0], f[1]};
		f[0] = f[1] = 0;
		if (c[i] >> bit & 1) {
			upd(f[0], 1LL * g[1] * subset(c[i] & lim, bit) % mod);
			upd(f[1], 1LL * g[0] * subset(c[i] & lim, bit) % mod);
		}
		int tmp = ((1LL << 31) - 1) ^ (1 << bit);
		int number = (c[i] >> bit & 1) ? (1 << bit) : c[i] & lim;
		upd(f[0], 1LL * g[0] * subset(number, bit) % mod);
		upd(f[1], 1LL * g[1] * subset(number, bit) % mod);
	}
	return f[0];
}

int solve() {
	int ans = 0;
	for (int i = 30; i >= -1; --i) {
		if (i == -1) {
			++ans;
			break;
		}
		int xr = 0;
		for (int j = 1; j <= n; ++j) {
			xr ^= (c[j] >> i & 1);
			if (c[j] >> i & 1) {
				upd(ans, calc(i, j));
			}
		}
		if (xr != 0) break;
	}
	return ans;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
	}
	int ans1 = solve();
	for (int i = 1; i <= n; ++i) {
		--c[i];
	}
	int ans2 = solve();
	upd(ans1, mod - ans2);
	cout << ans1 << endl;
	return 0;
}

[51nod 1261] 上升数

题意

求长度为 $n$ 的十进制数个数 $x$ ，满足：

从高位到低位， $x$ 数位上的数单调不降；
$x$ 是给定整数 $k$ 的倍数。

数据范围： $n≤1e18,k≤500$ ，答案对 $1e9+7$ 取模

题解

注意到 $x$ 可以被表示为不超过九个形如 $111.....1$ 的数字的和。

考虑数列 $1,11,111...$ ，他们模 $k$ 的值不超过 $k$ 次就会出现循环。

于是可以对于模 $k$ 的值做一个分组背包。计 $f_{i,j,l}$ 为考虑了模 $k$ 为 $0..i$ 的数，选出来的数和模 $k$ 为 $j$ ，选出来的数个数为 $l$ 的方案数。

转移需要先处理出一个 $num_i$ 表示那个数列前 $n$ 项中模 $k$ 为 $i$ 的数的个数。从 $num_i$ 个元素的可重集中选择 $r$ 个元素的方案数是 $\dbinom{num_i+r-1}{r}$ ，可以 $O(r)$ 计算。

对于环的处理比较恶心，细节可以看代码。

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 505;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

LL n, k, las;
LL fac[N], fav[N], inv[N];
LL vis[N], num[N], ord[N], d[N];

void init() {
	read(n); read(k);
	fac[0] = fav[0] = 1;
	inv[1] = fac[1] = fav[1] = 1;
	for (int i = 2; i < N; ++i) {
		inv[i] = -mod / i * inv[mod % i] % mod + mod;
		fac[i] = fac[i - 1] * i % mod;
		fav[i] = fav[i - 1] * inv[i] % mod;
	}
	
	LL cnt = 1, now = 1, len = 0, beg = -1;
	d[1] = 0;
	vis[now] = 1;
	while (1) {
		if (vis[(now * 10 + 1) % k]) {
			len = d[now] - d[(now * 10 + 1) % k] + 1;
			beg = (now * 10 + 1) % k;
			break;
		}
		d[(now * 10 + 1) % k] = d[now] + 1;
		now = (now * 10 + 1) % k;
		vis[now] = 1;
	}
	
	cnt = 0;
	LL x = 0;
	while ((cnt + 1) <= n && (x * 10 + 1) % k != beg) {
		x = (x * 10 + 1) % k;
		++num[x];
		++cnt;
	}
	if (cnt == n) las = x;
	else {
		n -= cnt;
		LL tot = n / len;
		x = (x * 10 + 1) % k;
		num[x] = tot;
		while ((x * 10 + 1) % k != beg) {
			x = (x * 10 + 1) % k;
			num[x] = tot;
		}
		cnt = len * tot;
		while (cnt + 1 <= n) {
			++cnt;
			x = (x * 10 + 1) % k;
			++num[x];
		}
		las = x;
	}
	--num[las];
}

LL C(LL x, int y) {
	if (y == 0) return 1;
	if (x < y) return 0;
	LL ans = 1;
	for (LL i = x; i > x - y; --i) {
		ans = ans * (i % mod) % mod;
	}
	ans = ans * fav[y] % mod;
	return ans;
}

inline void upd(LL &x, register LL y) {
	static LL z;
	x = ((z = x + y) >= mod) ? z - mod : z;
}

void solve() {
	static LL dp[N][N][10];
	for (int i = 0; i < 10; ++i) {
		dp[0][0][i] = C(num[0] + i - 1, i);
	}
	for (int i = 0; i < k - 1; ++i) {
		for (int j = 0; j < k; ++j) {
			for (int l = 0; l < 10; ++l) {
				for (int d = 0; d + l < 10; ++d) {
					LL del = dp[i][j][l] * C(num[i + 1] + d - 1, d) % mod;
					upd(dp[i + 1][(j + d * (i + 1)) % k][l + d], del);
				}
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int l = 1; l + j < 10; ++l) {
				if ((i + l * las) % k == 0) {
					LL del = dp[k - 1][i][j];
					upd(ans, del);
				}
			}
		}
	}
	cout << ans << endl;
}

int main() {
	init();
	solve();
	return 0;
}

[51nod 1321] 记分牌

题意

$N$ 个选手参加一场比赛，赛制为循环赛，每 $2$ 个人都要比 $1$ 场，获胜的人得到 $1$ 分，失败的人不得分。比赛结束后会有一个积分榜，每个选手都有一个总的积分。

然而，某些选手的积分成绩被擦掉了。那么根据剩下的数据，由你统计一下，积分榜共有多少种不同的情况。其中被擦掉的成绩用 $-1$ 表示。

例如 $3$ 个选手的积分为： $-1 ,-1, 2$ ，那么存在 $2$ 种情况： $0 ,1 ,2;1, 0, 2$ 。由于结果很大，输出 $Mod \; 1000000007$ 的结果即可。

题解

似乎又是一道难点不在 $DP$ 上的 $DP$ 题……

主要是要知道一个定理：Landau’s Theorem

Landau’s Theorem

定义一个竞赛图的比分序列(score sequence)，是把竞赛图的每一个点的出度从小到大排列得到的序列。

一个长度为 $n$ 的序列 $s=(s_1≤s_2,≤...≤s_n)$ ， $n≥1$ ，是合法的比分序列当且仅当：

$\forall 1 ≤ k ≤ n, \sum_{i=1}^{k} s_i ≥ \dbinom{k}{2}$

特殊的， $k=n$ 时上式取等号。

证明可以看看：这篇blog

大概后面的就不用说了？

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long longblog
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 42;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

LL T, n;
LL fac[N], fav[N], inv[N];
int a[N], sum[N];

void init() {
	fac[0] = fav[0] = 1;
	inv[1] = fac[1] = fav[1] = 1;
	for (int i = 2; i < N; ++i) {
		inv[i] = -mod / i * inv[mod % i] % mod + mod;
		fac[i] = fac[i - 1] * i % mod;
		fav[i] = fav[i - 1] * inv[i] % mod;
	}
}

LL C(LL x, int y) {
	if (x < y) return 0;
	return fac[x] * fav[y] % mod * fav[x - y] % mod;
}

inline void upd(int &x, register int y) {
	static LL z;
	x = ((z = x + y) >= mod) ? z - mod : z;
}

void solve() {
	static int dp[N][N * N][N];
	memset(a, 0, sizeof a);
	memset(dp, 0, sizeof dp);
	read(n);
	for (int i = 1; i <= n; ++i) {
		int x; read(x);
		if (x >= 0) ++a[x];
		else ++a[n + 1];
	}
	sum[0] = a[0];
	for (int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + a[i];
	}
	for (int i = 0; i <= a[n + 1]; ++i) {
		dp[0][0][i] = C(a[n + 1], i);
	}
	for (int i = 0; i < n; ++i) {
		for (int k = 0; k <= a[n + 1]; ++k) {
			int use = sum[i] + a[n + 1] - k;
			for (int j = C(use, 2); j <= n * n; ++j) {
				if (!dp[i][j][k]) continue;
				int num = j, flag = 1, cnt = use;
				for (int l = 1; l <= a[i + 1]; ++l) {
					++cnt;
					num += i + 1;
					if (C(cnt, 2) > num) flag = 0;
				}
				if (!flag) continue;
				for (int l = 0; l <= k; ++l) {
					upd(dp[i + 1][num][k - l], C(k, l) * dp[i][j][k] % mod);
					++cnt;
					num += i + 1;
					if (C(cnt, 2) > num) break;
				}
			}
		}
	}
	cout << dp[n][C(n, 2)][0] << endl;
}

int main() {
	init();
	read(T);
	while (T--) solve();
	return 0;
}

[51nod 1230] 幸运数

题意

如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。

例如： $120$ 是幸运数，因为 $120$ 的数字之和为 $3$ ，平方和为 $5$ ，均为质数，所以 $120$ 是一个幸运数字。

给定 $x$ ， $y$ ，求 $x$ ， $y$ 之间（包含 $x$ ， $y$ ，即闭区间 $[x,y]$ ）有多少个幸运数。

数据范围： $T≤10000$ 组数据， $1≤x≤y≤1e18$

题解

数位 $DP$ 裸题，应该没什么好讲的。

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1500;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

int ispri[N];
int tot, a[N];
LL f[20][200][N];

void init() {
	memset(ispri, 1, sizeof ispri);
	ispri[0] = ispri[1] = 0;
	for (int i = 2; i < N; ++i) {
		if (!ispri[i]) continue;
		for (int j = i + i; j < N; j += i) {
			ispri[j] = 0;
		}
	}
	memset(f, 0xff, sizeof f);
}

LL dfs(int x, int sum, int sqr, int limit) {
	if (!x) {
		if (ispri[sum] && ispri[sqr]) return 1;
		else return 0;
	}
	if ((!limit) && (~f[x][sum][sqr])) return f[x][sum][sqr];
	LL ans = 0;
	for (int i = 0; i < 10; ++i) {
		if (limit && i > a[x]) break;
		ans += dfs(x - 1, sum + i, sqr + i * i, limit & (i == a[x]));
	}
	if (!limit) f[x][sum][sqr] = ans;
	return ans;
}

int main() {
	init();
	int T; read(T);
	while (T--) {
		LL x, y, s1, s2;
		read(x); read(y);
		tot = 0;
		if (--x == 0) x = 1;
		while (x) {
			a[++tot] = x % 10;
			x /= 10;
		}
		s1 = dfs(tot, 0, 0, 1);
		tot = 0;
		while (y) {
			a[++tot] = y % 10;
			y /= 10;
		}
		s2 = dfs(tot, 0, 0, 1);
		printf("%lld\n", s2 - s1);
	}
	return 0;
}

[51nod 1250] 排列与交换

题意

给定一个数组 $A = [1, 2, 3, ..., n]$ 。

对 $A$ 进行好恰好 $k$ 次相邻交换，能得到多少个不同的序列 ( $S1$ )？

对 $A$ 进行最多 $k$ 次交换（不需要相邻），你能得到多少个不同的序列 ( $S2$ )？

给出数组 $A$ 的长度 $N$ ，以及次数 $K$ ，求 $S1$ 和 $S2$ 。由于结果很大，输出 $Mod \; 1000000007$ 的结果。

数据范围： $n,k≤3000$

题解

对于 $S1$ ，只需要求 $n$ 个数有 $k-2t$ 个逆序对的全排列数量就好了。 $2t$ 那部分可以通过不断交换两个数浪费掉，剩下的把冒泡排序的交换倒着做回去就好了。

对于 $S2$ ，就是求有多少个排列可以通过不超过 $k$ 次操作变成 $1..n$ 。容易发现一个排列需要的最少次数就是所有轮换大小 $-1$ 的和，加入一个数考虑是加入到一个轮换使费用 $+1$ 还是新建一个轮换使费用不变即可。

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 3005;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

inline int add(register int x, register int y) {
	static int z;
	return ((z = x + y) >= mod) ? (z - mod) : z;
}

inline int sub(register int x, register int y) {
	return (x < y) ? (x - y + mod) : (x - y);
}

int n, m;
int f[N][N], g[N][N];

namespace Subtask1 {
	int main() {
		memset(f, 0, sizeof f);
		memset(g, 0, sizeof g);
		f[0][0] = 1;
		for (int i = 0; i <= m; ++i) {
			g[0][i] = 1;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= m; ++j) {
				f[i][j] = g[i - 1][j];
				if (j - i >= 0) {
					f[i][j] = sub(f[i][j], g[i - 1][j - i]);
				}
			}
			g[i][0] = f[i][0];
			for (int j = 1; j <= m; ++j) {
				g[i][j] = add(g[i][j - 1], f[i][j]);
			}
		}
		int ans = 0;
		for (int i = m; i >= 0; i -= 2) {
			ans = add(ans, f[n][i]);
		}
		return ans;
	}
}

namespace Subtask2 {
	int main() {
		memset(f, 0, sizeof f);
		f[0][0] = 1;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= m; ++j) {
				f[i + 1][j] = add(f[i + 1][j], f[i][j]);
				f[i + 1][j + 1] = add(f[i + 1][j + 1], 1LL * f[i][j] * i % mod);
			}
		}
		int ans = 0;
		for (int i = 0; i <= m; ++i) {
			ans = add(ans, f[n][i]);
		}
		return ans;
	}
}

int main() {
	read(n); read(m);
	printf("%d %d\n", Subtask1::main(), Subtask2::main());
	return 0;
}

[51nod 1518] 稳定多米诺覆盖

题意

求用 $1*2$ 的多米诺骨牌覆盖 $n*m$ 的棋盘的方案数，使得任意一对相邻的行、列都至少有一个骨牌横跨。

数据范围： $n,m≤16$

题解

先预处理出一个 $dp_{i,j}$ 表示在不考虑任何限制的情况下，覆盖 $i*j$ 的棋盘的方案数。

容斥计算方案数。设 $f_i$ 为恰好有 $i$ 条横着的线没有被横跨，且所有竖着的线都被至少横跨一次的方案数； $g_i$ 为固定了 $i$ 条横着的线没有被横跨（其余线是否被横跨不确定），且所有竖着的线都被至少横跨一次的方案数。于是有：

$g_n = \sum_{i≥n} \dbinom{i}{n} f_n $

容斥一下可以得到：

$answer = f_0 = \sum_{i≥0} (-1)^i g_i$

于是我们枚举横着的线是否被固定为不被跨越，同样容斥处理竖着的线，但这部分可以用一个 $O(n^2)$ 的 $DP$ 处理。

设 $F_{i,j}$ 为最后一条被固定的线在第 $i$ 列后面，当前画的线条数的奇偶性为 $j$ 的方案数。为了方便计算，我们强制在第 $m$ 列后面固定一条线，这会使奇偶项的容斥系数翻转。

总复杂度是 $O(2^nn^2)$

#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 17;
const int mod = 1e9 + 7;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

inline int add(register int x, register int y) {
	static int z;
	return ((z = x + y) >= mod) ? (z - mod) : z;
}

inline int sub(register int x, register int y) {
	return (x < y) ? (x - y + mod) : (x - y);
}

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

int n, m;
int f[N][N][1 << N], g[N][N];
int s[N], dp[N][2], val[N], bitcnt[1 << N];
vector<int> vec;

void prework(int m) {
	int lim = (1 << m) - 1, high = (1 << m - 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			for (int k = 0; k < lim; ++k) {
				f[i][j][k] = 0;
			}
		}
	}
	f[0][0][lim - 1] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i == n - 1 && j == m - 1) continue;
			if (j != m - 1) {
				for (int k = 0; k <= lim; ++k) {
					if (!f[i][j][k]) continue;
					if (~k & high) {
						upd(f[i][j + 1][k << 1 | 1], f[i][j][k]);
					}
					else {
						upd(f[i][j + 1][(k ^ high) << 1], f[i][j][k]);
						if (~k & 1) {
							upd(f[i][j + 1][(k ^ high ^ 1) << 1 | 1], f[i][j][k]);
						}
					}
				}
			}
			else {
				for (int k = 0; k <= lim; ++k) {
					if (!f[i][j][k]) continue;
					if (~k & high) {
						upd(f[i + 1][0][k << 1 | 1], f[i][j][k]);
					}
					else {
						upd(f[i + 1][0][(k ^ high) << 1], f[i][j][k]);
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		g[i][m] = f[i - 1][m - 1][lim];
	}
}

void solve() {
	memset(s, 0, sizeof s);
	for (int i = 0; i < (1 << n - 1); ++i) {
		bitcnt[i] = bitcnt[i >> 1] + (i & 1);
		vec.clear();
		int cnt = 0;
		for (int j = 0; j < n; ++j) {
			++cnt;
			if ((i >> j & 1) || (j == n - 1)) {
				vec.push_back(cnt);
				cnt = 0;
			}
		}
		for (int j = 1; j <= m; ++j) {
			val[j] = 1;
			for (int k = 0; k < vec.size(); ++k) {
				val[j] = 1LL * val[j] * g[vec[k]][j] % mod;
			}
		}
		memset(dp, 0, sizeof dp);
		dp[0][1] = 1;
		for (int j = 1; j <= m; ++j) {
			for (int k = 0; k < j; ++k) {
				upd(dp[j][0], 1LL * dp[k][1] * val[j - k] % mod);
				upd(dp[j][1], 1LL * dp[k][0] * val[j - k] % mod);
			}
		}
		int ans = sub(dp[m][0], dp[m][1]);
		upd(s[bitcnt[i]], ans);
	}
	
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		if (i & 1) upd(ans, mod - s[i]);
		else upd(ans, s[i]);
	}
	cout << ans << endl;
}

int main() {
	n = 16, m = 16;
	for (int i = 1; i <= m; ++i) prework(i);
	while (~scanf("%d%d", &n, &m)) solve();		
	return 0;
}