http://acm.zju.
题目链接
题目:
There are n people standing in a row. And There are m numbers, 1.2...m. Every one should choose a number. But if two persons standing adjacent to each other choose the same number, the number shouldn't equal or less than k. Apart from this rule, there are no more limiting conditions.

And you need to calculate how many ways they can choose the numbers obeying the rule.

Input

There are multiple test cases. Each case contain a line, containing three integer n (2 ≤ n ≤ 108), m (2 ≤ m ≤ 30000), k(0 ≤ k ≤ m).

Output

One line for each case. The number of ways module 1000000007.

Sample Input

4 4 1
Sample Output

216
这是英文.大家用翻译软件大概能知道大概意思,还有就是输出的时候要取余1000000007
还有就是我的代码

#include"stdio.h"
#define MM 1000000007
__int64 mk(int m,int k);
int main()
{
    int n,m,k,i;
    __int64 s,su;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        s=mk(m,k);
        for(i=1,su=1;i<=n-1;i++)
        {
            su*=s;
            su=su%MM;        
        }
        printf("%I64d\n",su);
    }
    return 0;
}
__int64 mk(int m,int k)
{
    int i;
    __int64 su;
    for(i=1,su=0;i<=m;i++)
    {
        if(i-k-1>0)
        su+=i-k-1;
        if(m-i-k>0)
        su+=m-i-k;
    }
    return su;
}

我自己编译没有错误
但交上去就说我编译错误
错误说明是
p.c:3: error: expected '=', ',', ';', 'asm' or '__attribute__' before 'mk'
p.c: In function 'main':
p.c:19: error: '__int64' undeclared (first use in this function)
p.c:19: error: (Each undeclared identifier is reported only once
p.c:19: error: for each function it appears in.)
p.c:19: error: expected ';' before 's'
p.c:22: error: 's' undeclared (first use in this function)
p.c:22: warning: implicit declaration of function 'mk'
p.c:23: error: 'su' undeclared (first use in this function)
这有点看不懂
求解释

[ 本帖最后由 Magic_July 于 2013-5-5 21:04 编辑 ]

而且说下编译的环境是G++

看来OJ不支持__int64（估计是linux服务器），换成long long。

试了试 long long int
果断可以了
不过然后果断的超时了

O(n*m)的时间复杂度，再看看n和m的范围，运算量在万亿次这个数量级，必然超时。

一般acm的题目每组数据的运算量要控制在百万量级以内，超过这个级别大多都会超时。

昨晚想了一下这题，分治处理可以做到O(m * log(n))，十万量级的运算量，可用。

具体方案，将长度为n的可行序列划分成m个以i打头以i结尾的以及m个以i打头不以i结尾的集合进行二分运算。

已经晕了.

你的代码好屌，求思路O(∩_∩)O