hdu 5459(2015沈阳网赛) Jesus Is Here

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目;http://acm.hdu.edu.cn/showproblem.php?pid=5459

题意给出一组字符串,每个字符串都是前两个字符串相加而成,求第n个字符串的c的各个坐标的差的和,结果要模530600414.

很容易看出字符串的长度及c的个数都是由斐波那契数列构成的,得到最后结果是ans[i]=ans[i-1]+ans[i-2]+x,要求的就是x

假设第n项中字符'c'的个数为cn，字符'c'坐标之和为sn，字符串长度为ln

当形成第i个字符串的时候对于第i-1个字符串来说,这个串里的每个’c‘所增加的值为i-2中’c‘的反向坐标（就是串长 - 坐标，记为cc ），即c2*（c1*l1-s1）；（把c1*n1-s1 拆分成一个一个的c相加，就相当于c1个cc相加）

对于第i-2个字符串来说就是每个’c‘所增加的值就为i-1中’c‘的坐标，即c1*s2

两者之和就是x

这题当输入3或者4的时候都输出0或者都输出1的时候都可以,就是说后端数据中没有3和4折两组

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 int mod=;

 ll ans[],c[],s[],l[];

 int main()

 {

     int t,n,i,sum;

     ans[]=;ans[]=;

     c[]=;s[]=;l[]=;

     c[]=;s[]=;l[]=;

     for (i=;i<=;i++)

     {

         ans[i]=(((ans[i-]+ans[i-])%mod+c[i-]*s[i-])%mod+((c[i-]*l[i-]-s[i-])%mod*c[i-])%mod)%mod;

         l[i]=(l[i-]+l[i-])%mod;

         c[i]=(c[i-]+c[i-])%mod;

         s[i]=((s[i-]+s[i-])%mod+l[i-]*c[i-])%mod;

     }

     ans[]=,ans[]=;//所以这一步要不要无所谓

     while (~scanf("%d",&t))

     {

         sum=;

         while (t--)

         {

             scanf("%d",&n);

             printf("Case #%d: %I64d\n",sum++,ans[n]);

         }

     }

     return ;

 }