1 条题解
-
1XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2024-08-08 19:25:58
题目大意
有 \(n\) 台电脑排成一排。每次可以手动开启一台。若某台电脑未开启且它两侧的电脑均开启,则它会自动开启。求开启所有电脑的方案数。两种方案不同当且仅当对应的手动开启电脑的序列不同。
数据范围: \(3 \leqslant n \leqslant 400\) 。解 - 参考这篇题解
如图:
那么我们需要处理的情况有两种:BBB片段和BGB片段Part 1: BBB序列
所以手动开启长度为 \(n\) 的电脑的方案数为
\[ C^1_{n-1} + C^2_{n-1} + ... + C^{n-1}_{n-1} = 2^{n-1} \]Part 2: BGB序列
答案即:\[ \sum^n_{i=0} f[n][i] \]
\(i, j, k\)均通过枚举得到用Windows画图花了好久,给个赞吧qwq
Code
#include<bits/stdc++.h> using namespace std; const int N = 4e2 + 10; long long C[N][N] , bit[N]; long long n , m , ans , f[N][N]; void init(int mod) { bit[0] = 1; for(int i = 1 ; i <= N - 10 ; i ++) bit[i] = bit[i - 1] * 2 % mod; for(int i = 0 ; i <= N - 10 ; i ++) { C[i][0] = 1; for(int j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; } } signed main() { cin >> n >> m; init(m); for(int i = 1 ; i <= n ; i ++) { f[i][i] = bit[i - 1]; for(int j = 0 ; j <= i ; j ++) { for(int k = 1 ; k + i + 1 <= n; k ++) { f[i + 1 + k][j + k] += f[i][j] * bit[k - 1] % m * C[j + k][k] % m; f[i + 1 + k][j + k] %= m; } } } for(int i = 0 ; i <= n ; i ++) ans += f[n][i] , ans %= m; cout << ans << '\n'; return 0; }
- 1
信息
- ID
- 1063
- 难度
- (无)
- 分类
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者