| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3490 人关注过本帖, 1 人收藏
标题:浙大ACM ZOJ Problem Set - 3690
只看楼主 加入收藏
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
结帖率:100%
收藏(1)
已结贴  问题点数:20 回复次数:6 
浙大ACM ZOJ Problem Set - 3690
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 编辑 ]
搜索更多相关主题的帖子: persons test multiple numbers people 
2013-05-05 21:01
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
收藏
得分:0 
而且说下编译的环境是G++
2013-05-05 21:13
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:20 
看来OJ不支持__int64(估计是linux服务器),换成long long。

重剑无锋,大巧不工
2013-05-05 21:20
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
收藏
得分:0 
回复 3楼 beyondyf
试了试 long long int
果断可以了
不过然后果断的超时了
2013-05-05 21:27
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
O(n*m)的时间复杂度,再看看n和m的范围,运算量在万亿次这个数量级,必然超时。

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

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

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

重剑无锋,大巧不工
2013-05-06 10:33
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
收藏
得分:0 
回复 5楼 beyondyf
已经晕了.
2013-05-06 19:38
lynlyn
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2014-11-30
收藏
得分:0 
回复 2 楼 Magic_July
你的代码好屌,求思路O(∩_∩)O
2014-11-30 21:32
快速回复:浙大ACM ZOJ Problem Set - 3690
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026934 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved