题目链接：
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，否则等式不会成立
贴代码：
1 #include <cstdio> 2 #include <cstring> 3 #define N 1000007 4 char a[N]; 5 int main() 6 { 7 // freopen("in.c","r",stdin); 8 int n; 9 scanf("%d",&n); 10 for(int i=0; i<n; ++i) 11 { 12 scanf("%s",a); 13 // printf("%s ",a); 14 int len=strlen(a); 15 int cnt =0; 16 if(a[0] !='M') 17 { 18 printf("No "); 19 continue; 20 } 21 bool flag = true; 22 for(int j=1; j<len; ++j) 23 { 24 if(a[j] == 'M') 25 { 26 flag = false; 27 break; 28 } 29 if(a[j] == 'U') 30 cnt += 3; 31 else 32 ++cnt; 33 } 34 if(!flag) 35 { 36 printf("No "); 37 continue; 38 } 39 if(cnt == 1) 40 { 41 printf("Yes "); 42 continue; 43 } 44 // printf("cnt=%d ",cnt); 45 if(cnt%6 == 2 || cnt%6 == 4) 46 flag =true; 47 else flag =false; 48 if(flag) 49 printf("Yes "); 50 else 51 printf("No "); 52 } 53 return 0; 54 }