acdream 1039: cxlove is a good man 左右子树规律题

解题思路:

　　对于每一个节点有三个值来唯一标志( L, cur, R ) 分别表示 左上根, 本身, 右上根

　　对于两种走法:

　　　　向左走, 左上根不变, 右上根更新        表达式为:  L = L,  R = ( L + R )

　　　　向右走, 右上根不变, 左上根更新　　表达式为:  L = ( L + R ),  R = R

　　当向走或向右走 N 步时,  可得 N*L + R 或  L + N*R

　　数据过大,需使用64int, 使用按位模拟乘法避免溢出

解题代码:

#include<stdio.h>
const int N = 10000007;
const int mod = 1000000007;
typedef long long LL;

struct node{
    LL l, r, cur;
}fenzi,fenmu;

LL mul( LL a, LL b ){
    LL res = 0;
    while( b ){
        if( b&1 ) if( (res+=a) >= mod ) res -= mod;
        a <<= 1; if( a >= mod ) a -= mod;
        b >>= 1;
    }
    return res;
}
int main(){
    int T;    
    while( scanf("%d", &T) != EOF) {
        char op[2]; 
        LL n;
        fenzi.l = 0, fenzi.r = 1, fenzi.cur = 1;
        fenmu.l = 1, fenmu.r = 0, fenmu.cur = 1;
        while( T-- )
        {
            scanf("%s %lld",op, &n);
            if( op[0] == 'L' )
            {
                if( n ) 
                {
                    fenzi.r = ( mul( n%mod, fenzi.l ) + fenzi.r ) % mod;
                    fenmu.r = ( mul( n%mod, fenmu.l ) + fenmu.r ) % mod;
                }
            }
            if( op[0] == 'R' )
            {
                if( n )
                {
                    fenzi.l = ( mul( n%mod, fenzi.r ) + fenzi.l ) % mod;
                    fenmu.l = ( mul( n%mod, fenmu.r ) + fenmu.l ) % mod;
                }
            }
        }
        fenzi.cur = (fenzi.l+fenzi.r) % mod;
        fenmu.cur = (fenmu.l+fenmu.r) % mod;
        printf("%lld/%lld\n", fenzi.cur, fenmu.cur );
    }
    return 0;
}