最新消息:点击查看大S的省钱秘笈

Vijos P1093 文科生的悲哀 C语言版

Vijos题解 Slyar 111浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

背景 Background

化学不及格的ET无奈选择了文科。他必须硬着头皮准备一次又一次的文科考试。

描述 Description

在这一学期一共有n次文科考试,考试科目有4种,分别为政治、历史、地理和综合。每次考哪一科是不定的,因此在考试前ET不知道应该去复习哪 一科的功课。他希望能预测出下一次可能考的科目。于是,他收集到了以往的文科考试的资料。从以往的考试中,他发现了这样几个规律:

1.如果这次考的是政治,那么下一次一定会考历史;
2.如果这次考的是综合,那么下一次一定会考地理;
3.如果这次考的是历史,那么下一次要么考政治,要么考地理;
4.如果这次考的是地理,那么下一次要么考历史,要么考综合。

ET已经知道,本学期的第一次考试科目为政治。他打算拟定一个可以应对所有可能情况的应考复习计划。因此,他想知道,整个学期有多少种可能的考试科目安排满足以上规律。

输入格式 Input Format

一个正整数n,代表本学期总的考试次数。
输入数据保证n<=10000。

输出格式 Output Format

一个正整数,表示符合规律的科目安排方案的总数。
考虑到这个结果可能会很大,因此你只需要输出它mod 7654321的值即可。

Tip:不知道他们怎么看出来是Fibonacci数列的,以后发现这样的题得先推推前几项,然后不完全归纳。。。需要注意每次加的时候都除以mod 7654321,否则会越界。

下面是证明:

f(n)=a(n)+b(n)    a表示历史或地理(生成双科的) b表示政治或综合(生成单科)
a(n)=f(n-1)    无论单科还是双科都会生成一个双科
b(n)=a(n-1)    第N次的单科是第N-1次双科生成的
即 f(n)=a(n)+b(n)=f(n-1)+a(n-1)=f(n-1)+f(n-2)

#include <stdio.h>

int main(){
int n,i;
long x[10001];
scanf("%d",&n);
x[1]=1;
x[2]=1;
for (i=3;i<=n;i++) x[i]=(x[i-1]+x[i-2])%7654321;
printf("%d",x[n]);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1093 文科生的悲哀 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (3)

  1. 我一定要想明白....
    本拉九8年前 (2008-11-02)回复
  2. 为什么mod 7654321 而不mod 别的数呢?
    本拉九8年前 (2008-11-02)回复
    • 问出题的人去,别问我~
      Slyar8年前 (2008-11-02)回复