学步园

 打表找规律，推出了公式，但是各种调试还是不过

最后发现在公式里有一个除法，而对相应的取模操作忘处理了，导致一直WA到比赛结束都没调出来

以后要注意这个问题了。。。

这题类似高中的排列组合里的传球问题， 甲乙丙丁4人传球，从甲传n次到甲 和从甲传n次到乙丙丁的个数即为所要求的分段的个数。

能够推出公式分别自己到自己和自己到其他人2种 ， 分奇偶2种公式

            if ( Node[i].s == Node[i-1].s )
            {
                temp = ((3*(cal_3( t ) +(t&1?1:(-1))) )%mod)/4;
                //这里的除法一开始没注意，凡涉及和除法有关的mod都要处理下，要记住这次教训
                ans = ans * temp%mod_;
            }
            else if ( Node[i].s != Node[i-1].s)
            {
                temp = (((cal_3( t+1 ) -(t&1?1:(-1))) )%mod)/4;
                ans = ans * temp%mod_;
            }

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef unsigned long long ll;
const ll mod=4*1000000007ll;
const ll mod_=1000000007ll;
ll pow3[100];//3^(2^i);

long long cal_3( int n )
{
    //cout << n << endl;
    ll res=1;
    for (int t=0 ; n ; n>>=1 ,t++ )
        if(n&1)res=res*pow3[t]%mod;
    //cout << res << endl;
    return res;
}

struct node {
char s ;
int loc;
}Node[15];
bool cmp ( node a, node b )
{
    return a.loc < b. loc;
}

int main()
{
    int n , m;
    char c;
    ///
    pow3[0]=3;
    for (int i=0 ; i<50 ;++i)
    {
        pow3[i+1]=pow3[i]*pow3[i]%mod;
        //printf("%lld  %lld\n",pow3[i] * pow3[i] ,pow3[i+1]);
    }
    ///
    //freopen ("in.txt" , "r" , stdin);
    //freopen ("out.txt" , "w" ,stdout );
    while (scanf("%d%d",&n , &m ) != EOF )
    {
        if(m==0){cout <<(4*cal_3(n-1)%mod_) <<endl;continue;}
        for ( int i = 0 ; i < m ; i ++ )
        {
            scanf("%d%c%c" ,&Node[i].loc, &c ,&Node[i].s );
        }

        long long ans = 1;
        sort ( Node , Node + m , cmp );

        ans = ans*cal_3(Node[0].loc-1 )%mod_;
        //cout << ans << endl;
        for ( int i = 1 ; i < m ; i ++ )
        {
            int t = (Node[i].loc - Node[i-1].loc -1 );
            long long temp;

            if ( Node[i].s == Node[i-1].s )
            {
                temp = ((3*(cal_3( t ) +(t&1?1:(-1))) )%mod)/4;
                //这里的除法一开始没注意，凡涉及和除法有关的mod都要处理下，要记住这次教训
                ans = ans * temp%mod_;
            }
            else if ( Node[i].s != Node[i-1].s)
            {
                temp = (((cal_3( t+1 ) -(t&1?1:(-1))) )%mod)/4;
                ans = ans * temp%mod_;
            }
        }
        ans = ans*cal_3( n - Node[m-1].loc )%mod_;
        //printf("%d\n", ans%mod );
        cout << (ans % mod_ ) << endl;
    }
    return 0;
}