学步园

http://acm.hust.edu.cn/problem.php?cid=1106&pid=7

题意：

给一张纸A面向上，可上下左右折叠，折完后展开，输出A面外凸折痕的条数；

#include<iostream>
#include<cstdio>
 
using namespace std;
 
char ch[2000000];
 
int main()
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
               scanf("%s",ch);
               long long x=0,y=0,tmp=1;
               for(int i=0;ch[i];i++)
               {
                       if(ch[i]=='D' || ch[i]=='U')
                       {
                               y=(y+tmp/2)%100000009;
                               x=(x*2)%100000009;
                       }
                       else
                       {
                               x=(x+tmp/2)%100000009;

                               y=(y*2)%100000009;
                       }
                       tmp*=2;

                       tmp%=(100000009*2);
               }
               printf("%lld\n",(x+y)%100000009);
        }
        return 0;

}