Description
题库链接
给出一个 \(1\times n\) 的棋盘, 棋盘上有 \(k\) 个棋子, 一半是黑色, 一半是白色最左边是白色棋子, 最右边是黑色棋子, 相邻的棋子颜色不同
小 \(A\) 可以移动白色棋子, 小 \(B\) 可以移动黑色的棋子, 他们每次操作可以移动 \(1\sim d\) 个棋子
每当移动某一个棋子时, 这个棋子不能跨越两边的棋子, 当然也不可以出界当谁不可以操作时, 谁就失败了
小 \(A\) 和小 \(B\) 轮流操作, 现在小 \(A\) 先移动, 问有多少种初始棋子的布局使他胜利
- \(1\leq n\leq 10000,1\leq k\leq 100\)
- Solution
是一道假题... 参考了 黄学长的做法 ... 具体可以参见他的博客
- Code
- #include <bits/stdc++.h>
- using namespace std;
- const int yzh = 1000000007, N = 10000;
- int n, k, d, a[N+5], b[N+5], bin[20], f[16][N+5];
- int C(int n, int m) {return 1ll*a[n]*b[m]%yzh*b[n-m]%yzh; }
- void work() {
- scanf("%d%d%d", &n, &k, &d);
- a[0] = b[0] = a[1] = b[1] = bin[0] = 1;
- for (int i = 2; i <= n; i++) b[i] = -1ll*yzh/i*b[yzh%i]%yzh;
- for (int i = 2; i <= n; i++) a[i] = 1ll*i*a[i-1]%yzh, b[i] = 1ll*b[i]*b[i-1]%yzh;
- for (int i = 1; i < 20; i++) bin[i] = (bin[i-1]<<1);
- f[0][0] = 1;
- for (int i = 0; i < 15; i++)
- for (int j = 0; j <= n-k; j++)
- for (int p = 0; p*(d+1) <= k/2 && p*(d+1)*bin[i]+j <= n-k; p++)
- (f[i+1][p*(d+1)*bin[i]+j] += 1ll*f[i][j]*C(k/2, p*(d+1))%yzh) %= yzh;
- int ans = C(n, k);
- for (int i = 0; i <= n-k; i++)
- (ans -= 1ll*f[15][i]*C(n-k/2-i, k/2)%yzh) %= yzh;
- printf("%d\n", (ans+yzh)%yzh);
- }
- int main() {work(); return 0; }
来源: http://www.bubuko.com/infodetail-2537625.html