负担集训-Test6（多校联合训练-1）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------
依旧垫底
复旦怎么会收我（们）这么菜的学生啊_(:з」∠)_
---------------------------------------------------
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)
---------------------------------------------------
评论 (0)
