Artifact Content
Not logged in

Artifact aa7e1a1a6f23a9b69de7885d42784009acc510b3


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

LL MODVAL = 1000000007LL;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
LL POW(LL x, LL e) {
	LL v = 1;
	for(;e;x=MUL(x,x),e>>=1)
		if(e&1)
			v = MUL(v, x);
	return v;
}

class IOIString { public:
	string  s;
	LL nI, nQ;

	int countIOIs(vector <string> mask) 
	{
		s  = accumulate( mask.begin(), mask.end(), string("") );
		nI = count( s.begin(), s.end(), 'I' );
		nQ = count( s.begin(), s.end(), '?' );

		return SUB( POW(2,nQ), non_IOI() );
	}

	LL non_IOI()
	{
		LL ans = 0;
		if( nI == 0 ) ans = ADD(ans,  1); // #I == 0
		if( nI == 0 ) ans = ADD(ans, nQ); // #I == 1
		if( nI == 1 ) ans = ADD(ans,  1); // #I == 1
		for(int D=1; D<s.size(); D+=2)
			for(int S=0; S<D; ++S)
				ans = ADD(ans, non_IOI_2(S, D)); // #I >= 2
		return ans;
	}

	LL non_IOI_2( int S, int D )
	{
		string t;
		for(int i=S; i<s.size(); i+=D)
			t += s[i];

		// t 以外の部分は全部 'O' でないとダメ
		if( count(t.begin(), t.end(), 'I') < nI )
			return 0;

		// t は /O*II+O*/ にマッチしないとダメ。4状態のオートマトンでDP
		LL q0=1, q1=0, q2=0, q3=0;
		for(int i=0; i<t.size(); ++i)
		{
			LL p0 = (t[i]=='O' ?         q0 : t[i]=='I' ?          0 : q0);
			LL p1 = (t[i]=='O' ?          0 : t[i]=='I' ?         q0 : q0);
			LL p2 = (t[i]=='O' ?          0 : t[i]=='I' ? ADD(q1,q2) : ADD(q1,q2));
			LL p3 = (t[i]=='O' ? ADD(q2,q3) : t[i]=='I' ?          0 : ADD(q2,q3));
			q0=p0, q1=p1, q2=p2, q3=p3;
		}
		return ADD(q2, q3);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, IOIString().countIOIs(mask));}
int main(){

CASE(0)
	string mask_[] = {"IO?"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 1; 
END
CASE(1)
	string mask_[] = {"????"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 4; 
END
CASE(2)
	string mask_[] = {"?II"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 0; 
END
CASE(3)
	string mask_[] = {"I??O??I"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 16; 
END
CASE(4)
	string mask_[] = {"???I???????O???","???????????O??IO????????I???"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 438952513; 
END
CASE(5)
	string mask_[] = {"?"};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 0; 
END
CASE(6)
	string mask_[] = {
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
"??????????????????????????????????????????????????",
};
	  vector <string> mask(mask_, mask_+sizeof(mask_)/sizeof(*mask_)); 
	int _ = 967087276; 
END
}
// END CUT HERE