hust校赛 1614 折叠纸张觅凸痕

hust校赛 1614 折叠纸张找凸痕

       One day, god Sheep gets an AK(all kill) in a contest, so he is very boring, then he just plays with a paper. The paper has two faces called A and B. Sheep finds the paper can be folded for infinity times, and now Sheep thinks the paper is interesting, so he tries to fold the paper in half for many times. He finds out he has four way to make the paper folded in half, there are listed below:
 
图片请见 PDF版题目。


At first, god Sheep keeps the face A of the paper faced to him,and he fold the paper for many times. In the end, Sheep opens up the paper, and keeps the face A faced to him again. Now the question is : How many creases on the face A of the paper are protruding? God sheep solves the question without 2 seconds. Can you?  You should make your anwser mod 100000009.

       The first line of input contains a single positive integer N , which means the number of test cases. The following N lines gives N non-empty strings containing only characters in "UDLR", which is the sequences of the actions of the Sheep to fold paper. The length of the each string is a positive number less than 10^6.

       For each case output the anwser mod 100000009 in a line.

4LLRDLURULULL

011022

http://acm.hust.edu.cn/problem.php?id=1614

/*题意： 一张纸可以向上向下向左向右对折   问对于A面    连续折后 产生的凸折纹的个数思路：上下一样  左右一样   然后可以分析出  对折后 凸折纹于凹折纹的数量是对称的  中间的那道折纹不算  所以只要看半张纸产生的折纹数即可在只看半张的时候 假设第一次折是L   对于LR  对折n次可产生2^（n-1）-1道折纹(s1)   对于D U 对折n次  可产生2^n-1条折纹(s2)则总凸折纹为 (s1+1)*s2+(s2+1)*s1  */#include<stdio.h>#include<string.h>int len;const long long mod=100000009;char s[1000000+10];long long optimized_pow_n(long long x,long long n,long long m)//求x的n次方对m 求余{    long long ret=1;    while(n)    {        if(n&1)        {            ret=(long long)(ret*x)%m;        }        x=x*x%m;        n>>=1;    }    return ret;}int main(){    int i,flag;    long long s1,s2,n1,n2;    int cas;    scanf("%d",&cas);    while(cas--)    {        long long ans=1;        flag=0;n1=n2=0;        scanf("%s",s);        len=strlen(s);        if(s[0]=='L'||s[0]=='R')            flag=1;        for(i=0;i<len;i++)        {            if(s[i]=='R'||s[i]=='L') n1++;            else n2++;        }        if(flag==0)        {            long long temp=n1;            n1=n2;            n2=temp;        }        s1=1;        n1--;/*        while(n1--)        {             s1*=2%mod;        }        s1--;        s2=1;        //n2--;        while(n2--)        {            s2*=2%mod;        }        s2=s2-1;*/        s1=optimized_pow_n(2,n1,mod);//我用上面的方法求2的n次方(对mod求余) 提交是错误的  但是用 这个方法就是正确的        s1--;                        //很疑惑  求大神解释        s2=optimized_pow_n(2,n2,mod);        s2--;        ans=((long long)(s1+1)*s2%mod+(long long)(s2+1)*s1%mod)%mod;        printf("%lld\n",ans);    }} /* 反思:   求n的x次方对m求余的时候不要直接自己写 用上面的那个算法  很快 也不会出错 一开始我遇到这个题 就一直在用纸折   但是很耗费时间   找到一些规律后 可以思考一下  是否可以在纸上画画  来回的折叠 很耗费时间 以后遇到类似的题目 折是必要的 但是绝对不能一个劲的去折 要思考下 总结下规律 不要去盲目的折 */