首页 > ACM题库 > HDU-杭电 > HDU 4732-Round Table-计算几何-[解题报告]HOJ
2015
09-17

HDU 4732-Round Table-计算几何-[解题报告]HOJ

Round Table

问题描述 :

I have m little buddies, and tonight we will have a fancy dinner in my room.
Fortunately, I have a round table which is large enough for all my little buddies. (As for me, I will not sit in the round table for some reasons) And the round table is so large that I will not let my little buddies sit shoulder to shoulder.
That means I will select m seats from n seats, and there maximal length of consecutive seats in the original round table won’t be larger than or equal to k. I want know how many different ways I can choose.
Here is one more thing, two ways are considered the same if and only if one can be obtained by rotation.
Minimum palindrome

The answer may be very large so the answer should modulo 109 + 7.

输入:

The first line has a number T (T <= 200) , indicating the number of test cases.
Next each line contain three integer n, m, k (1 <= n <= 105, 1 <= m <= 105, 2 <= k <= 105, m <= n).

输出:

The first line has a number T (T <= 200) , indicating the number of test cases.
Next each line contain three integer n, m, k (1 <= n <= 105, 1 <= m <= 105, 2 <= k <= 105, m <= n).

样例输入:

3
3 1 2
5 2 2
8 3 2

样例输出:

Case #1: 1
Case #2: 1
Case #3: 2

题目链接:: http://acm.hdu.edu.cn/showproblem.php?pid=4732
代码链接:: https://github.com/Ronnoc/Training/blob/master/Hdu/4732.cpp
Round Table
N个点成环,选择M个点,最长连续选取长度要小于K.

(1<=M<=N<=10^5,2<=K<=10^5)
在旋转同构的意义下种数有多少

解:

选取的点称为黑点

不选取的点称为白点

对白点无约束

黑点有M个,白点就有N-M个,特判掉N==M的情况

记n=N-M

对每个白点,以它为起点展开,记第i个起点后黑点的个数为x[i]

则可以转化为x[1]+…+x[n]=M且0<=x[i]<K在旋转同构下的种数

先不考虑旋转同构

我们可以采用容斥原理的办法得到不考虑同构时的结果为Z=∑Comb(n,i)*(-1)^i*z[i]

其中z[j]表示x[1]+…+x[n]=M,x[i]非负且有j个数>=K的种数

以n=8,M=4,K很大为例

在Z中和40000000同构的出现了8次

和11001100同构的出现了4次

和10101010同构的只出现了2次

我们接下来要做的事情就是去重

记g(u)表示以长度u为循环节的种数

记f(u)表示以长度u为最小循环节的种数

有g(u)=∑_{d|u}f(d)

由mobius反演公式可得f(u)=∑_{d|u}\miu[d]*g(u/d)

真正要求的答案是Ans=∑f(i)/i

我们带入并采用一些手段化简公式可以得到

Ans=∑_{u|gcd(n,M)}∑_{d|n/u}\miu[n/(ud)]*g(d)*u/n

这部分可以做的很快了,但是具体的复杂度我也没有花时间去算…


//感谢叉姐告诉,b的我循环节的事情…

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ronnoc/article/details/41664303