AT2664 [AGC017A] Biscuits 题解
2024-09-06 02:17:26
Content
有一个长度为 \(n\) 的数列 \(a\)。你希望从中选出一些数,使得这些数的和对 \(2\) 取模后的结果为 \(P\)。求方案数。
数据范围:\(1\leqslant n\leqslant 50\),\(0\leqslant P\leqslant 1\),\(1\leqslant a_i\leqslant 100\)。
Solution
做完之后转了一圈,发现本题题解区现有题解全部都是 dp 做法。所以本人在这里来一发无脑数数做法。
不难发现,对于某组数,其和的奇偶性只和这组数中奇数的个数有关。如果奇数的个数为奇数,这组数的和就是奇数,否则就是偶数。
知道这个东西之后,这道题目就很简单了。我们先统计出数列 \(a\) 中的奇数个数 \(k\)。然后我们先考虑取多少个偶数,再考虑取多少个奇数。但是取奇数的时候要注意:如果 \(k\bmod 2\neq P\),奇数就只能够取奇数个,否则就只能取偶数个。至于偶数你随便取多少个都可以。
因此,我们可以分类讨论求出式子:
- \(k\bmod 2=P\),此时奇数只能够取偶数个,因此方案数为 \(\sum\limits_{i=0}^k\sum\limits_{j=0}^{n-k}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}n-k\\j\end{pmatrix}[2\mid i]\)。
- \(k\bmod 2\neq P\),此时奇数只能够取奇数个,因此方案数为 \(\sum\limits_{i=0}^k\sum\limits_{j=0}^{n-k}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}n-k\\j\end{pmatrix}[2\nmid i]\)。
其中 \([x]\) 表示条件 \(x\) 是否为真,如果为真其值为 \(1\),否则为 \(0\)。
当然,代码实现中,我们可以灵活运用 for
循环,这样,既不用判断条件,也不需要分类讨论去求。详情请结合代码理解。
Code
日常用 #define int ll
偷懒(
namespace Solution {
#define int ll
int n, p, cnt0, cnt1, ans, a[57], C[57][57];
iv Main() {
F(int, i, 0, 50) { //预处理组合数
C[i][0] = 1;
F(int, j, 1, i) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
read(n, p);
F(int, i, 1, n) read(a[i]), cnt0 += !(a[i] & 1), cnt1 += a[i] & 1;
F(int, i, 0, cnt0) Fo(int, j, ((cnt1 & 1) != p), cnt1, 2) ans += C[cnt0][i] * C[cnt1][j];
write(ans);
return;
}
#undef int
}
最新文章
- mysql join 和left join 对于索引的问题
- C语言程序设计第9堂作业
- Facebook Messenger的后台架构是什么样的?
- Python自动化之select解析
- Codeforces Round #195 A B C 三题合集 (Div. 2)
- mouseover,mouseout,mouseenter,mouseleave的区别
- 第三周作业、实时操作系统µC/OS介绍及其它内容
- Gridview中将某列的背景设置为绿色
- iOS计算文本高度
- iOS 退出应用程序
- 6)图[2]Prim算法[最小生成树]
- Android 启动过程的底层实现
- Python——Flash框架——用户认证
- Linux根据MAC地址自动设置IP
- java Swing小知识点
- Asp .Net core 2 学习笔记(2) —— 中间件
- UEditor整合代码高亮插件SyntaxHighlighter
- python-------打印与字符串格式化
- Unity 3D 之Playerprefs
- POJ Cow Exhibition