首页 > ACM题库 > HDU-杭电 > hdu 2065 “红色病毒”问题-母函数-[解题报告]C++
2013
12-29

hdu 2065 “红色病毒”问题-母函数-[解题报告]C++

“红色病毒”问题

问题描述 :

医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.

输入:

每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.

输出:

每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.

样例输入:

4
1
4
20
11
3
14
24
6
0

样例输出:

Case 1: 2
Case 2: 72
Case 3: 32
Case 4: 0

Case 1: 56
Case 2: 72
Case 3: 56

题意:易理解…

分析:容易看出可以用指数型母函数来求解,但是由于结果太大,然后题目要求求出后面两位即可,于是我就在想应该会有周期性,与之我就用母函数求出了前20的值,

经过观察确实是有规律的,然后就水过了,后来我看了别人的解题报告发现很多人用dp做的,真心碉堡了!!

代码实现:

#include<stdio.h>
#include<string.h>
int main()
{
    int T,i;
    int a[6]={1,2,6,20,72,72};
    int b[5][4]={{56,60,12,92},{56,0,52,12},{56,40,92,32},{56,80,32,52},{56,20,72,72}};
    __int64 n,m;
    while(scanf("%d",&T)!=EOF&&T)
    {
        for(i=1;i<=T;i++)
        {
            scanf("%I64d",&n);
            printf("Case %d: ",i);
            if(n<=5)
                printf("%d\n",a[n]);
            else
            {
                m=(n-6)%4;
                n=((n-6)/4)%5;
                printf("%d\n",b[n][m]);
            }
        }
        printf("\n");
    }
    return 0;
}

 上面是我自己做的,后来我又看了下别人的解题思路,真心牛B!!

思路:由指数型母函数的知识f(x)=(1+x/1!+x^2/2!+x^3/3!…+x^n/n!)^2+(1+x^2/2!+x^4/4!+x^6/6!…+…)^2;又由大学的泰勒公式:e^x=1+x/1!+x^2/2!+x^3/3!…+x^n/n!;e^(-x)=1-x/1!+x^2/2!-x^3/3!+…-…;所以e^x+e^(-x)=1+x^2/2!+x^4/4!+x^6/6!…+…;

所以: f(x)=e^(2x) * ((e^x+e^(-x))/2)^2
 = (1/4) * e^(2x) * (e^(2x) + 2 + e^(-2x))
 = (1/4) * (e^(4x) + 2*e^(2x) +1)
   = (1/4) * ( (1+4x/1!+(4x)^2/2!+(4x)^3/3!+…+(4x)^n/n!) + 2*(1+2x/1!+(2x)^2/2!+(2x)^3/3!+…+(2x)^n/n!) +1)

得:  x^n 项系数 

a(n)  = (1/4) * ((4x)^n/n! + 2*(2x)^n/n!)
 = (1/4) * ( 4^n*x^n/n! + 2^(n+1)*x^n/n!)
 = (4^(n-1) + 2^(n-1)) * x^n/n!

即所求 F(n) = (4^(n-1) + 2^(n-1)) % 100.

类似的题:poj 3734

代码实现:

#include<stdio.h>
#include<string.h>
int haha(int a,__int64 b)//同余取模
{
   int sum=1;
   while(b)
   {
      if(b&1)
          sum=(sum*a)%100;
      a=(a*a)%100;
      b=b>>1;
   }
   return sum;
}
int main()
{
    int T,i,temp;
    __int64 n;
    while(scanf("%d",&T)!=EOF&&T)
    {
        for(i=1;i<=T;i++)
        {
            scanf("%I64d",&n);
            printf("Case %d: ",i);
            if(n==0)
                printf("%d\n",1);
            else
            {
                temp=(haha(2,n-1)+haha(4,n-1))%100;
                printf("%d\n",temp);
            }
        }
        printf("\n");
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/jiangjing/archive/2013/04/17/3026863.html


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  4. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  5. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。