负担集训-Test6(多校联合训练-1)

---------------------------------------------------
依旧垫底 
复旦怎么会收我(们)这么菜的学生啊_(:з」∠)_
---------------------------------------------------

D:
就是说有k堆石子围成一个圈,初始每堆石子都有n个,现在从第一堆开始,顺时针不断地从石子堆中拿掉一些,要求拿掉之后这堆石子的数量是原来的数量的约数,直到有某一堆石子数量为1为止,问对于每堆石子,在拿完他之后游戏结束(即他是最先变为1的石子堆)的操作有多少种
n以这样的形式给出:首先给出n的质约数个数m,接下来给出m个质数以及其指数e[i]
m,k<=10,sigma(e[i])<=10000,有5组数据sigma(e[i])<=100000,一共两百组数据
 
首先我们只需求出p[i]表示对于一堆n个的石子,拿了i次,刚好拿完的方案数
答案就是Sigma(i)(p[i+1]^(j-1))(p[i+2]^(k-j+1))
因为必须把一堆石子变成他的约数,所以实际上p[u]都可以看做是有m堆石子,每堆有e[i]个,每次可以从任意多堆中取任意多个,但至少要取一个,这样恰好u次取完的方案数
那么我们可以假设q[u][v]表示对于一堆v个石子,每次取任意多个(可以不取),取恰好u次取完的方案数
使用插板法,显然q[u][v] = C(v+u-1,v)
再假设h[u]表示有m堆石子,每堆有e[i]个,每次可以从任意多堆中取任意多个,可以不取,这样恰好u次取完的方案数
那么就有h[u] = Pi(q[u][e[i]])
现在考虑利用h来求出p
容斥一下,用总方案数-至少空了1行的方案数+至少空了两行的方案数-...
显然至少空了a行的方案数就是h[u-a]*C(u,v)
因此就有p[n] = Sigma(i)(h[i]*C(n,i)*(-1^(n-i)))
把C(n,i)拆开成n!/(i!(n-i)!)
然后就很容易发现原式是个卷积,因此一个NTT就行了
---------------------------------------------------
F:
题意是说给你一个长度为n的排列a和一个长度为b的排列b,问有多少个数论函数f:[1,n]∩N->[1,m]∩N满足:
f[i] = b[f[a[i]]]({f[i]}不一定等于[1,m]∩N,是子集也可以)
n,m<=100000
 
以i->a[i]这个关系建立有向图,因为每个点最多只有一个出边,所以每个点要么在环上,要么是某个环的小尾巴,显然只要一个环上一个点确定了,那么这个环以及他的小尾巴都确定了,并且这个取值在b中对应的点必须在一个大小是这个环的约数的环上,因此去a,b中分别找环就行了
---------------------------------------------------
H:
题意是说给你n个数,有m个询问,每次询问第k[i]+1小的数是哪一个
询问满足若k[i]!=k[j],k[i]<k[l],k[j]<k[l]那么k[i]+k[j]<=k[l]
n<=10^7,10组询问,m<=100
 
首先看询问满足的性质,发现他最坏情况下是一个斐波那契数列
因此可以使用stl中的std::nth_element,这个函数是O(n)的,他每次会把第k小的元素放到k这个位置,且比他小的在他左边,比他大的在他右边
首先把询问降序排序,每次在[1,k[i+1]]这个范围询问就行了
设f是斐波那契数列,那么这个算法的复杂度就是Sigma(f[i]<=n)f[i] = O(n)
---------------------------------------------------