有 $n$ 个人, 有些人说真话, 有些人说假话, 每个人都知道所有人是说假话的还是说真话的, 现在问他们每一个人: 说真话的人有多少. 每个人都会给出一个答案. 说假话的人会随便给出[1,n]中的一个数, 但不会给出真实的答案. 现在, 给你两个数 $n, K$, 问你有多少种方案, 能确定恰好有 $K$ 个人说谎. 保证 $n$ 是 $2$ 的幂, 答案模 $777777777$.
$1 \le K \le n \le 2^8, n = 2^p$
假设有 $x$ 个人说真话, 那么会有正好 $x$ 个人给出答案 $x$.
但是会有同时发生的情况 $y$ 个人给出答案 $y$, 这样我们就不能确定到底是 $x$ 个人还是 $y$ 个人说谎了.
所以这种方案不能算.
也就是说, 要求仅有一个数$x$, 满足正好 $x$ 个人给出答案 $x$.
求方案数, 考虑dp.
我们可以用组合数学的思路来想, 有 $n$ 个空, 每个空需要填一个数字, 要求满足有$x$个位置填的是$x$
$dp(i, j, k)$ 表示填入了 $[1, i]$ 个数字在 $j$ 个空中, 其中 $k$ 个人说假话.
方程就是
$$dp(i, j, k) = \binom{n-j+m}{m} (\sum_{m=0}^k dp(i-1, j-m, k-m) \cdot [m \ne i] + \sum_{m=0}^j dp(i-1, j-m, k) \cdot [m=i])$$
写的时候注意常规的dp细节, 比如不存在的状态, 不合法的枚举(负数)等等.
这样是 $O(n^4)$ 的, 过不了.
但是 $n$ 的取值很小, 所以……
$$\Huge\text{打表}$$
复杂度$O(1)$ (doge)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
const int P = 777777777;
const int MAXN = 300;
int C[MAXN][MAXN];
int Plus(LL a, LL b) {
return a + b >= P ? (a + b) % P : a + b;
}
int Mult(LL a, LL b) {
return a * b >= P ? a * b % P : a * b;
}
int n = 1<<8, K = 0;
int dp[MAXN][MAXN][MAXN];
void init() {
for(int i = 0; i <= n; i++)
for(int j = C[i][0] = 1; j <= i; j++)
C[i][j] = Plus(C[i - 1][j - 1], C[i - 1][j]);
}
int main() {
init();
printf("Table[9][(1<<8)+1] = {\n");
for (int p = 0; p <= 8; p++) {
n = 1<<p;
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= j; k++)
for (int m = 0; m <= j; m++) {
if (m != i) {
if (m <= k)
dp[i][j][k] = Plus(dp[i][j][k], Mult(C[n-j+m][m], dp[i-1][j-m][k-m]));
}
else
dp[i][j][k] = Plus(dp[i][j][k], Mult(C[n-j+m][m], dp[i-1][j-m][k]));
}
printf("{");
for (int k = 0; k <= n; k++)
printf("%d%c", dp[n][n][k], ",}"[k==n]);
printf("%c\n", ",}"[p==8]);
}
return 0;
}
|