团体比赛。
完了完了完了科目三考试要拖到小学期里了我现在心情是崩溃的
牛客第五场比赛的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}$$
为所求答案。
比赛的时候没有看这道题。看题解生成函数的开头,便照葫芦画瓢的做了一遍。
还有,处理阶乘的逆的手段——倒着处理很巧妙,值得好好参考。
比赛如上。
牛客多校第六场的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个数全体是解题的关键。
牛客多校第五场的E题。
置换、圈、最小公倍数、高精度。
对于给定置换,求它在置换群中的阶。(高精度取模)
分解成k个不相交的轮换,求轮换长的最小公倍数。
为了避过高精度,练习了Java的BigInteger类。