首页 > ACM题库 > HDU-杭电 > HDU 3503-Perfect Sequence-栈-[解题报告]HOJ
2014
04-09

HDU 3503-Perfect Sequence-栈-[解题报告]HOJ

Perfect Sequence

问题描述 :

A sequence <a0, a1, a2, …, an> of integers is called a perfect sequence when all the partial sums a0, a0 + a1, a0 + a1 + a2, …, a0 + a1 + … + an are all positive.
Let�s consider a specific sequence <a0, a1, a2, …, amn>, (ai = 1 or ai = (1-m), 1 ÷ i ÷ (m*n) ) , whose total sum is 1. Actually you can easily deduce that there are n occurrences of (1-m). So how many of these sequences are perfect sequences.

输入:

Input contains several testcases.
For each test case, you will be given n, m (1 ÷ m, n ÷ 100000) in a single line.
Process to the end of the file.

输出:

Input contains several testcases.
For each test case, you will be given n, m (1 ÷ m, n ÷ 100000) in a single line.
Process to the end of the file.

样例输入:

4 2
5 2
3 4

样例输出:

14
42
22

原创,转帖需注明。

昨天做的一次比赛,刚开始一道数论一次AC,不过之后的perfect sequence让我郁闷了很长时间。

题意让我联想到Catalan数,Catalan数:对于给定的n个数,进行n次进栈和n次出栈操作,一共存在多少种不同的进出栈序列,结果显然是C(n,2n)/(n+1)..本题题意近似于:给定n个(1-m)和(nm-n+1)个1,使得方程a1+a2+a3+~~ai+~~anm+1=1,其中ai只能去(1-m)和1。问方程有多少组不同的解。比赛之后我一直向这个方向考虑,但是始终没有想法,之后考虑Catalan数的递归定义,忘了,所以一直不过。

之后研究了一下,发现题目的趣味性:如果a0 + a1 + … + an = 1, 则<a0, a1, …, an>, <a1, a2, …, an, a0>, <a2, a3, …, an, a0, a1>…<an, a0, a1, …, an-1>中有且只有一个是perfect sequence.

那么题目中所有满足题意的序列有C(mn+1, n)个,可以将这些序列按照循环分组,可以证明每个组中恰有mn+1个(就是说不可能出现一个序列循环少于mn+1次又变回自己,理由是mn+1和n互质),这样恰有C(mn+1, n)/(mn+1)个序列是perfect的。再有: 对质数p, 有1/a = a^(p-2) (mod p)(费马小定理)。

代码如下:

#include <iostream>
using namespace std;

const __int64 Mod=100000007;

__int64 mod_exp(__int64 a,__int64 b0,__int64 n=Mod)
{
if( a > n )
   a %= n;
__int64 i, d = 1, b[35];

for( i=0; i < 35; ++i )
{
   b[i] = b0%2;
   b0 /= 2;
   if( b0 == 0 )
    break;
}

for( ;i >= 0; –i )
{
   d = (d*d)%n;
   if( b[i] == 1 )
    d = (d*a)%n;
}
return d;
}

__int64 solve (__int64 n,__int64 m)
{
__int64 ans=1;

for (__int64 i=m*n+2-n;i<m*n+1;i++)
{
   ans=((((ans*i)%Mod)*mod_exp(i-m*n+n-1,Mod-2)))%Mod;
}

ans=(ans*mod_exp(n,Mod-2))%Mod;

return ans;
}

int main ()
{
__int64 n,m;

while (scanf ("%I64d%I64d",&n,&m)!=EOF)
{
   printf ("%I64d\n",solve(n,m));
}

return 0;
}

参考:http://hi.baidu.com/halstead/item/765eed4b2f5e06eb1281da65


,
  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  4. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count