A.生成字符串 (syoj.1761) 洛谷
P6191 [USACO09FEB] Bulls And Cows S
首先单独统计只有 0 - 1 个 1 的答案；
另所求序列由 "1000" 这样的形式再加一个 1 构成，设当前统计的有 i 个 1，此时序列长度 j 为 (k + 1) * (i - 1) + 1。如果所需序列长度已经超过限制便跳出。
否则计算$$C^i_{n-j+(i-1)+1}$$
意为把每一段中 "1000" 这样的整体及最后的一个 1 先删掉，此时序列中剩下的是散的 0。然后把删掉的整体中形如 "000" 这样的整段 0 看做一个新的整体，共有 (i - 1) 个，一一加回来。所以只用在整段 0 和散 0 中将 1 找空插入。（此时就不用考虑那个 0 究竟是散的还是整段了，因为整段个数和 1 的个数相互限制，0 一视同仁，空位一定是能正好放开 1 的。）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 5000011;
int n, k;
ll ans = 1;
ll fac(ll x)
{
ll tot = 1;
for(int i = 2; i <= x; i ++ ) tot = tot * i % mod;
return tot;
}
ll pmod(ll a, ll b)
{
ll tot = 1;
while(b)
{
if(b & 1) tot = (tot * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return tot;
}
ll C(ll x,ll y)
{
if(x < y) return 0;
return fac(x) * pmod(fac(y), mod - 2) % mod * pmod(fac(x - y), mod - 2) % mod;
}
int main()
{
scanf("%d%d", &n, &k);
ans += n;
for(int i = 2; i <= n; i ++ )
{
int j = (k + 1) * (i - 1) + 1;
if(j > n) break;
if(j == n)
{
ans = (ans + 1 + mod) % mod;
break;
}
else ans = (ans + C(n - j + (i - 1) + 1, i) + mod) % mod;
}
printf("%lld", ans % mod);
}
B.农夫与牛 (syoj.1762)
P1641 [SCOI2010] 生成字符串
不难看出是前两天上课刚讲的洛谷 P1641 生成字符串。
数形结合求出
\begin{aligned}
\frac{{C_{n+m}^m - C_{n+m}^{n+1}}}{C_{n+m}^m} =
\frac{n-m+1}{n+1}
\end{aligned}
另外提醒涉及到计算小数的问题容易在精度上寄掉，因此最好把式子化到最简。
#include<bits/stdc++.h>
using namespace std;
int T, n, m;
int main()
{
scanf("%d", &T);
while(T -- )
{
scanf("%d%d", &n, &m);
if(m > n) puts("0.000000");
else printf("%.6lf\n", (double)(n + 1 - m) / (n + 1));
}
return 0;
}
C.农夫与牛 (syoj.1763)
P3223 [HNOI2012] 排队
正难则反，补集转换。
先不考虑 Farmer John 和他的死对头 Farmer N 的限制算出答案，然后把 FJ 和 Farmer N 相邻的情况减掉。（这里我偷换了概念，应该是 Farmer John 和他的死对头 Farmer Nhoj，但。）
那么不考虑限制，两个农夫和他们可爱的奶牛就没有区别了。所有方案应是奶牛们的排列顺序 * 公牛排列顺序 * （一共有 n + 3 空）挑空把公牛放进去：
$${A_{n+2}^{n+2}} \times {A_m^m} \times {C_{n+3}^m}$$
两个死对头碰在一起那就坏事了，两个农夫就是一头奶牛！方案为俩农夫的顺序 * 奶牛们的排列顺序 * （共 n + 2 个空）挑空把公牛放进去：
$${{A_2^2} \times {A_{n+1}^{n+1}} \times {A_m^m} \times {C_{n+2}^m}}$$
作差。本题需要高精度所以不放码了（
D.农夫与牛 （syoj.1764）
P2592 [ZJOI2008] 生日聚会
发现数据范围很小，可以用 dp。
状态难定，多设几维。可以用 f[a][b][c][d] 来表示，当前选了 a 头公牛， b 头母牛。当前前缀中公牛最多比母牛多 c 头，母牛最多比公牛多 d 头。然后每次枚举状态看是否能转移，确定这个位置放公牛还是母牛并更新答案。注意加一或减一时都要和 0 比一下大小因为可能会出现全是公牛这样的情况。最后枚举符合条件的差统计答案。
显然 f[0][0][0][0] 这样的选择肯定存在一个方案。所以记得初始化。
#include<bits/stdc++.h>
using namespace std;
const int mod = 12345678;
int ans;
int n, m, k;
int f[155][155][25][25];
int main()
{
scanf("%d%d%d", &n, &m, &k);
f[0][0][0][0] = 1;
for(int i = 0; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
for(int x = 0; x <= k; x ++ )
for(int y = 0; y <= k; y ++ )
if(f[i][j][x][y])
{
int t = f[i][j][x][y];
f[i + 1][j][x + 1][max(y - 1, 0)] = (f[i + 1][j][x + 1][max(y - 1, 0)] + t) % mod;
f[i][j + 1][max(x - 1, 0)][y + 1] = (f[i][j + 1][max(x - 1, 0)][y + 1] + t) % mod;
}
for(int i = 0; i <= k; i ++ ) for(int j = 0; j <= k; j ++ ) ans = (ans + f[n][m][i][j]) % mod;
printf("%lld", ans);
return 0;
}
最近有点忙啊。
感觉一切都在 up up。