2015
05-23

There is a road from city A to city B.On the road,there are N positions(indexed from 0 to N-1).In order to celebrate the Multi-University training,the mayor of city A commands a worker to insert N flags on the N positions.The color of a flag is either red or green.We call the road is beautiful if and only if there exists at least one pair of non-negative integers (a,b) (0<=a<b<N and (a+b) is an even number) such that both a-th flag and b-th flag are red and (a+b)/2-th flag is green.Otherwise we call the road is ugly.Now,some positions have already been inserted flags.In order to make the road beautiful,the worker must carefully insert the flags on the positions which haven’t been inserted.He wants to know how many different types of beautiful road he can make.The type of the road only depends on the flags’ color.

The first line of the input is the number of cases. On each case there is a line consists of a string.The length of the string is N.(0<=N<=800).The i-th character of the string is ‘R’ or ‘G’ or ‘?’.'R’ means the flag on the i-th position which has been inserted is red.’G’ means the flag on the i-th position which has been inserted is green.’?’ means the i-th position hasn’t been inserted a flag.

The first line of the input is the number of cases. On each case there is a line consists of a string.The length of the string is N.(0<=N<=800).The i-th character of the string is ‘R’ or ‘G’ or ‘?’.'R’ means the flag on the i-th position which has been inserted is red.’G’ means the flag on the i-th position which has been inserted is green.’?’ means the i-th position hasn’t been inserted a flag.

4
?G
RG?
???
????

0
1
1
4

给出一个字符串，字符串由"R","G","?"组成，若字符串存在2R，且2R中间是一个G，则称该串为“漂亮串”，现考虑将"?"

所以我们可以枚举距离，构造“非漂亮串”，毛估总共需要枚举的次数为n*n*(1/1+1/2+…1/n)，时间复杂度为O(n^2logn),然后

就是我们把任意一个字符串s中的R全部提取出来（只考虑R），如果s不是beautiful
string

/*
Pro: 0

Sol:

date:
*/
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 1000000007
int t;
long long mod_pow(int a,int n,int p)
{
long long ret=1;
long long A=a;
while(n){
if (n & 1)
ret=(ret*A)%p;
A=(A*A)%p;
n>>=1;
}
return ret;
}
int main(){
scanf("%d",&t);
while( t -- ){
char str[808];
scanf("%s",str);
int len = strlen(str);
int unknown = 0, r_num = 0;
for(int i = 0; i < len; i ++){
if(str[i] == '?') unknown ++;
else if(str[i] == 'R') r_num ++;
}
long long unbea = (r_num == 0);//全为G的是不beautiful的。

for(int i = 0; i < len; i ++){//开始遍历
if(str[i] == 'R' || str[i] == '?'){//可能是R的情况
int x = (str[i] == 'R');
unbea = (unbea + (x == r_num) ) % mod;//这是给出的串只有一个R的情况

for(int dis = 1; dis + i < len; dis += 2){// + i 枚举距离
int y = x;
for(int sta = i + dis; sta < len; sta += dis){//枚举第二个位置以及以后
y += (str[sta] == 'R');
if(str[sta] == 'G') break;
unbea = (unbea + (y == r_num) )% mod;//如果遍历到的点和R的个数相同
//那么，就加上一个不美丽字符串
//这一句话包含了（拿样例4做解释）
//RRRR
//RRRG RRGG
//RGGR
//GRRR GRRG
//GGRR
}
}
}
}
printf("%I64d\n",mod_pow(2,unknown,mod) - unbea);
}
return 0;
}