2020-2021:teams:namespace:week_summary_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:week_summary_12 [2020/07/30 17:33] great_designer |
2020-2021:teams:namespace:week_summary_12 [2020/07/30 17:52] (当前版本) great_designer [本周推荐] |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| + | 牛客第五场比赛的C题。 | ||
| ===标签=== | ===标签=== | ||
| + | 生成函数。 | ||
| ===题意=== | ===题意=== | ||
| + | W先生正在写序列。如果他写两个长度为K的正整数序列A和B满足： | ||
| + | |||
| + | $$\sum_{i=1}^K a_i=N$$ | ||
| + | |||
| + | $$\sum_{i=1}^K b_i=M$$ | ||
| + | 他会得到: | ||
| + | |||
| + | $$P=\prod_{i=1}^K \min(a_i,b_i)$$ | ||
| + | |||
| + | 积分。 | ||
| + | |||
| + | 你想知道他能写的所有可能的序列的总分之和。 | ||
| ===题解=== | ===题解=== | ||
| + | 详细内容见第五场题解页面。通过计算，知道所求为多项式： | ||
| + | |||
| + | $$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$ | ||
| + | 之中$x^{N-K}y^{M-K}$前的系数。通过计算可知，该系数为： | ||
| + | |||
| + | $$\sum_{t=0}^{\min(N,M)-K} C_{K-1+t}^{K-1}C_{N-1-t}^{K-1}C_{M-1-t}^{K-1}$$ | ||
| + | |||
| + | 为所求答案。 | ||
| ===评论=== | ===评论=== | ||
| + | 比赛的时候没有看这道题。看题解生成函数的开头，便照葫芦画瓢的做了一遍。 | ||
| + | 还有，处理阶乘的逆的手段——**倒着处理**很巧妙，值得好好参考。 | ||
| ===== 胡湘鹏 ===== | ===== 胡湘鹏 ===== | ||
| 行 45: | 行 67: | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| + | 牛客多校第六场的E题。 | ||
| ===标签=== | ===标签=== | ||
| + | 数论、构造。 | ||
| ===题意=== | ===题意=== | ||
| + | 构造1到n的排列，模n意义下存在连续i个数和为k，对于任意的i从1跑到n。 | ||
| ===题解=== | ===题解=== | ||
| + | 首先，只有k为((n%2)?0:n/2)的时候有解。这是因为连续n个数必然是1到n全体，求和模n是固定的。 | ||
| + | 当n为奇数，构造为n 1 n-1 2 n-2 ……。 | ||
| - | ===评论=== | + | 当n为偶数，构造为n n/2 1 n-1 2 n-2 ……。 |
| + | ===评论=== | ||
| + | 优秀的构造题目，想到第一步考虑n个数全体是解题的关键。 | ||
| ===== 马逸行 ===== | ===== 马逸行 ===== | ||
| 行 72: | 行 98: | ||
| ===题目名称及来源=== | ===题目名称及来源=== | ||
| + | 牛客多校第五场的E题。 | ||
| ===标签=== | ===标签=== | ||
| + | 置换、圈、最小公倍数、高精度。 | ||
| ===题意=== | ===题意=== | ||
| + | 对于给定置换，求它在置换群中的阶。（高精度取模） | ||
| ===题解=== | ===题解=== | ||
| + | 分解成k个不相交的轮换，求轮换长的最小公倍数。 | ||
| ===评论=== | ===评论=== | ||
| + | 为了避过高精度，练习了Java的BigInteger类。 | ||
| ===== 页面链接 ===== | ===== 页面链接 ===== | ||
2020-2021/teams/namespace/week_summary_12.1596101580.txt.gz · 最后更改: 2020/07/30 17:33 由 great_designer
