题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4662
题目是问目标串能否由MI得到，我们可以逆向思维，目标串能否反过来处理得到MI，所以，首先排除M没有出现或者出现超过一次，或者只出现了一次但没有出现在第一个位置的情形····也就是说只剩下第一个位置是M，然后不再出现M的情形····
接下来思考如何得到I，既然要得到I，U必然要化成I，一个U相当于3个I，接下来还可以每次添加UU，相当于添加了6个I,这样当I的个数能凑成2^k,k>=0时，就是解
问题转化为如下：
关于x + 6*y = 2^k中x的整数解
问题描述：
当x取何值时，一定能找到一对y,k,其中y>=0,k>=0,y,k都是整数，来满足 x + 6*y = 2^k。
答案：
x= 1,或者x%6 =2 或者x%6 =4.
证明：
显然当x = 1时，y=0,z=0时满足条件，x=1是解。
现在只考虑x>1的情形。
当x>1时，如果x为解。
那么x = 2^k-6*y。k>0····
注意到8%6 = 2
那么k个2(k>0)相乘后的积%6 一定为2或4。
那么x%6 = (2^k-6*y)%6 = 2^k %6 = 2或4。
这就证明了如果x是解，要么x =1,否则x%6=2或4.
那么是不是凡是%6=2或4的就一定是解呢···答案是肯定的。
先考虑2+6*q的情形
2+6*q+6*y = 2^k
3(q+y)+1 = 2^p , p =k-1
注意要4%3=1，由此得到2^(2t)%3 = 1,2^(2t+1)%3 = 2.
上面的式子必然成立。
4+6*q的情形同样可以证明。
事实上，可以从另外一个角度思考，1必然是解,当x>=1时，如果(2^k-x)%6=2^k%6 - x%6 = 0,，注意到2^k%6=2或4，所以除非x%6=2或者4，否则等式不会成立
贴代码：
#include <cstdio>
#include <cstring>
#define N 1000007
char a[N];
int main()
{
// freopen("in.c","r",stdin);
int n;
scanf("%d",&n);
for(int i=; i<n; ++i)
{
scanf("%s",a);
// printf("%s\n",a);
int len=strlen(a);
int cnt =;
if(a[] !='M')
{
printf("No\n");
continue;
}
bool flag = true;
for(int j=; j<len; ++j)
{
if(a[j] == 'M')
{
flag = false;
break;
}
if(a[j] == 'U')
cnt += ;
else
++cnt;
}
if(!flag)
{
printf("No\n");
continue;
}
if(cnt == )
{
printf("Yes\n");
continue;
}
// printf("cnt=%d\n",cnt);
if(cnt% == || cnt% == )
flag =true;
else flag =false;
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return ;
}