没有任何变换（III变U和删UU操作）之前，I 的个数一定是2^x个（也就是2的整数次幂）
若仅考虑III变U，那么设U的个数为k，I 的个数变为2^x-3*k
再加上删除UU操作，假设我们删除了2*n个U，设实际U的个数为cntU, 则k=cntU+2*n
设 I 的实际个数为cntI，cntI = 2^x - 3*(cntU+2*n), n有解的情况为：
( 2^x - 3*cntU - cntI ) % 6 == 0
只要找到一个x满足这个条件即可，不过要注意( 2^x - 3*cntU - cntI )>=0，因为 -6%6 = 0，之前没有判断这里，WA的很惨……
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define LL long long int using namespace std; const int MAXN = ; LL cnt[];
char str[MAXN];
LL bit[]; bool check()
{
LL I = cnt[ 'I' - 'A' ];
LL U = cnt[ 'U' - 'A' ]; for ( int i = ; i < ; ++i )
{
if ( bit[i] - * U - I >= )
{
if ( ( bit[i] - * U - I ) % == )
return true;
}
}
return false;
} void init()
{
bit[] = ;
for ( int i = ; i < ; ++i )
bit[i] = ( bit[i - ] << );
return;
} int main()
{
init();
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%s", str );
int len = strlen(str);
memset( cnt, , sizeof(cnt) );
for ( int i = ; i < len; ++i )
++cnt[ str[i] - 'A' ];
if ( str[] != 'M' || cnt[ 'M' - 'A' ] != )
{
puts("No");
continue;
}
if ( check() ) puts("Yes");
else puts("No");
}
return ;
}