题目链接:https://codeforces.com/group/uVAsoW2Jkj/contest/324248/problem/H

题目大意:给数字n,用这n个数组成x个长度为n的不降序列序列(每个数使用次数为0-n),求x
例:n=2 ,可以组成11,22,12
玄学做法:列举出以1-n为结尾的序列的个数和总和,找数字之间的规律。
n 1 2 3 4 5 ……m
1 1
2 1+2=3
3 1+3+6 =10
4 1+4+10+20=35
5 1+5+15+35+70=126
可以看出:
1.加号左边的倒一数字和倒二数字是两倍关系
2.第一个数字都是1,第二个数字都是n
3.其他每个数字都是它左边和上面数字之和。
为什么
其实我也不知道
然后1+1=2的格式是不是很眼熟?杨辉三角啊
然后就斜着看能看出杨辉三角
然后就得出c(2n-1,n)
完美
正常解法
n个中取k个C(n,k)
将k个组合C(n-1,k-1)
将这两个组合数相乘并且将k为1-n的乘积求和
也是C(2n-1,n)
求逆元求C
(代码咕了)

Last modification:April 19, 2021
如果觉得我的文章对你有用,请随意投币