c9001fb21d 2011-08-20 kinaba: #include <iostream> c9001fb21d 2011-08-20 kinaba: #include <sstream> c9001fb21d 2011-08-20 kinaba: #include <iomanip> c9001fb21d 2011-08-20 kinaba: #include <vector> c9001fb21d 2011-08-20 kinaba: #include <string> c9001fb21d 2011-08-20 kinaba: #include <map> c9001fb21d 2011-08-20 kinaba: #include <set> c9001fb21d 2011-08-20 kinaba: #include <algorithm> c9001fb21d 2011-08-20 kinaba: #include <numeric> c9001fb21d 2011-08-20 kinaba: #include <iterator> c9001fb21d 2011-08-20 kinaba: #include <functional> c9001fb21d 2011-08-20 kinaba: #include <complex> c9001fb21d 2011-08-20 kinaba: #include <queue> c9001fb21d 2011-08-20 kinaba: #include <stack> c9001fb21d 2011-08-20 kinaba: #include <cmath> c9001fb21d 2011-08-20 kinaba: #include <cassert> c9001fb21d 2011-08-20 kinaba: #include <cstring> c9001fb21d 2011-08-20 kinaba: using namespace std; c9001fb21d 2011-08-20 kinaba: typedef long long LL; c9001fb21d 2011-08-20 kinaba: typedef complex<double> CMP; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: static const int MODVAL = 1000000007; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: struct UnionFind c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: vector<int> uf, sz; c9001fb21d 2011-08-20 kinaba: int nc; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: UnionFind(int N): uf(N), sz(N,1), nc(N) c9001fb21d 2011-08-20 kinaba: { for(int i=0; i<N; ++i) uf[i] = i; } c9001fb21d 2011-08-20 kinaba: int size() c9001fb21d 2011-08-20 kinaba: { return nc; } c9001fb21d 2011-08-20 kinaba: int Find(int a) c9001fb21d 2011-08-20 kinaba: { return uf[a]==a ? a : uf[a]=Find(uf[a]); } c9001fb21d 2011-08-20 kinaba: bool Union(int a, int b) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: a = Find(a); c9001fb21d 2011-08-20 kinaba: b = Find(b); c9001fb21d 2011-08-20 kinaba: if( a != b ) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: if( sz[a] >= sz[b] ) swap(a, b); c9001fb21d 2011-08-20 kinaba: uf[a] = b; c9001fb21d 2011-08-20 kinaba: sz[b] += sz[a]; c9001fb21d 2011-08-20 kinaba: --nc; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: return (a!=b); c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: }; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: struct mint c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: int val; c9001fb21d 2011-08-20 kinaba: mint():val(0){} c9001fb21d 2011-08-20 kinaba: mint(int x):val(x%MODVAL) {} c9001fb21d 2011-08-20 kinaba: mint(LL x):val(x%MODVAL) {} c9001fb21d 2011-08-20 kinaba: }; c9001fb21d 2011-08-20 kinaba: mint operator+(mint x, mint y) { return x.val+y.val; } c9001fb21d 2011-08-20 kinaba: mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } c9001fb21d 2011-08-20 kinaba: mint operator*(mint x, mint y) { return LL(x.val)*y.val; } c9001fb21d 2011-08-20 kinaba: mint POW(mint x, int e) { c9001fb21d 2011-08-20 kinaba: mint v = 1; c9001fb21d 2011-08-20 kinaba: for(;e;x=x*x,e>>=1) c9001fb21d 2011-08-20 kinaba: if(e&1) c9001fb21d 2011-08-20 kinaba: v=v*x; c9001fb21d 2011-08-20 kinaba: return v; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: class MagicalGirlLevelTwoDivOne { public: c9001fb21d 2011-08-20 kinaba: int theCount(vector <string> palette, int n, int m) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: if( (n^m)&1 ) c9001fb21d 2011-08-20 kinaba: return 0; c9001fb21d 2011-08-20 kinaba: int H = palette.size(); c9001fb21d 2011-08-20 kinaba: int W = palette[0].size(); c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: #define key(y,x) (2+(y)*W+(x)) c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: UnionFind uf(W*H+2); c9001fb21d 2011-08-20 kinaba: for(int y=0; y<H; ++y) c9001fb21d 2011-08-20 kinaba: for(int x=0; x<W; ++x) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: if( palette[y][x] != '.' ) c9001fb21d 2011-08-20 kinaba: uf.Union(key(y,x), (palette[y][x]-'0')%2); // 0:even, 1:odd c9001fb21d 2011-08-20 kinaba: if( y-n>=0 ) c9001fb21d 2011-08-20 kinaba: uf.Union(key(y,x), key(y-n,x)); c9001fb21d 2011-08-20 kinaba: if( x-m>=0 ) c9001fb21d 2011-08-20 kinaba: uf.Union(key(y,x), key(y,x-m)); c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: if( uf.Find(0) == uf.Find(1) ) c9001fb21d 2011-08-20 kinaba: return 0; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: vector< vector<int> > dep(n, vector<int>(m)); c9001fb21d 2011-08-20 kinaba: vector< vector<int> > stt(n, vector<int>(m)); c9001fb21d 2011-08-20 kinaba: for(int y=0; y<n; ++y) c9001fb21d 2011-08-20 kinaba: for(int x=0; x<m; ++x) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: for(int yy=y; yy<H; yy+=n) c9001fb21d 2011-08-20 kinaba: for(int xx=x; xx<W; xx+=m) c9001fb21d 2011-08-20 kinaba: if(palette[yy][xx] == '.') c9001fb21d 2011-08-20 kinaba: dep[y][x]++; c9001fb21d 2011-08-20 kinaba: int k = uf.Find(key(y,x)); c9001fb21d 2011-08-20 kinaba: if( k == uf.Find(0) ) c9001fb21d 2011-08-20 kinaba: stt[y][x] = 0; c9001fb21d 2011-08-20 kinaba: else if( k == uf.Find(1) ) c9001fb21d 2011-08-20 kinaba: stt[y][x] = 1; c9001fb21d 2011-08-20 kinaba: else c9001fb21d 2011-08-20 kinaba: stt[y][x] = 2; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: memo.assign(1024*10, -1); c9001fb21d 2011-08-20 kinaba: return rec(dep, stt, n, m, 0, 0); c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: vector<int> memo; c9001fb21d 2011-08-20 kinaba: int rec(const vector< vector<int> >& dep, const vector< vector<int> >& stt, const int H, const int W, c9001fb21d 2011-08-20 kinaba: int y, int status) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: if( y == H ) c9001fb21d 2011-08-20 kinaba: if( status == (1<<W)-1 ) c9001fb21d 2011-08-20 kinaba: return 1; c9001fb21d 2011-08-20 kinaba: else c9001fb21d 2011-08-20 kinaba: return 0; c9001fb21d 2011-08-20 kinaba: int me = status*H+y; c9001fb21d 2011-08-20 kinaba: if( memo[me] != -1 ) c9001fb21d 2011-08-20 kinaba: return memo[me]; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: mint total; c9001fb21d 2011-08-20 kinaba: for(int bits=0; bits<(1<<W); ++bits) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: mint cur(1); c9001fb21d 2011-08-20 kinaba: int odd = 0; c9001fb21d 2011-08-20 kinaba: for(int x=0; x<W; ++x) c9001fb21d 2011-08-20 kinaba: if( (bits>>x)&1 ) c9001fb21d 2011-08-20 kinaba: ++odd; c9001fb21d 2011-08-20 kinaba: int odddep = 0; c9001fb21d 2011-08-20 kinaba: int evendep = 0; c9001fb21d 2011-08-20 kinaba: if(odd%2 == 0) c9001fb21d 2011-08-20 kinaba: goto next; c9001fb21d 2011-08-20 kinaba: for(int x=0; x<W; ++x) c9001fb21d 2011-08-20 kinaba: if( stt[y][x] != 2 && stt[y][x] != ((bits>>x)&1) ) c9001fb21d 2011-08-20 kinaba: goto next; c9001fb21d 2011-08-20 kinaba: for(int x=0; x<W; ++x) c9001fb21d 2011-08-20 kinaba: { c9001fb21d 2011-08-20 kinaba: int d = dep[y][x]; c9001fb21d 2011-08-20 kinaba: (((bits>>x)&1) ? odddep : evendep) += d; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: cur = cur * POW(5, odddep); c9001fb21d 2011-08-20 kinaba: cur = cur * POW(4,evendep); c9001fb21d 2011-08-20 kinaba: cur = cur * rec(dep, stt, H, W, y+1, status^bits); c9001fb21d 2011-08-20 kinaba: total = total + cur; c9001fb21d 2011-08-20 kinaba: next:; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: return memo[me] = total.val; c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: }; c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: // BEGIN CUT HERE c9001fb21d 2011-08-20 kinaba: #include <ctime> c9001fb21d 2011-08-20 kinaba: double start_time; string timer() c9001fb21d 2011-08-20 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c9001fb21d 2011-08-20 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c9001fb21d 2011-08-20 kinaba: { os << "{ "; c9001fb21d 2011-08-20 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c9001fb21d 2011-08-20 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c9001fb21d 2011-08-20 kinaba: void verify_case(const int& Expected, const int& Received) { c9001fb21d 2011-08-20 kinaba: bool ok = (Expected == Received); c9001fb21d 2011-08-20 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c9001fb21d 2011-08-20 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c9001fb21d 2011-08-20 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c9001fb21d 2011-08-20 kinaba: #define END verify_case(_, MagicalGirlLevelTwoDivOne().theCount(palette, n, m));} c9001fb21d 2011-08-20 kinaba: int main(){ c9001fb21d 2011-08-20 kinaba: c9001fb21d 2011-08-20 kinaba: CASE(0) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"12", c9001fb21d 2011-08-20 kinaba: "2."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 2; c9001fb21d 2011-08-20 kinaba: int m = 2; c9001fb21d 2011-08-20 kinaba: int _ = 5; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(1) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"21", c9001fb21d 2011-08-20 kinaba: "1."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 2; c9001fb21d 2011-08-20 kinaba: int m = 2; c9001fb21d 2011-08-20 kinaba: int _ = 4; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(2) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"...", c9001fb21d 2011-08-20 kinaba: "...", c9001fb21d 2011-08-20 kinaba: "..."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 1; c9001fb21d 2011-08-20 kinaba: int m = 1; c9001fb21d 2011-08-20 kinaba: int _ = 1953125; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(3) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"..58..", c9001fb21d 2011-08-20 kinaba: "..47.."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 2; c9001fb21d 2011-08-20 kinaba: int m = 3; c9001fb21d 2011-08-20 kinaba: int _ = 0; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(4) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"...1.2.3", c9001fb21d 2011-08-20 kinaba: "4.5.6...", c9001fb21d 2011-08-20 kinaba: "...7.8.9", c9001fb21d 2011-08-20 kinaba: "1.2.3..."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 4; c9001fb21d 2011-08-20 kinaba: int m = 4; c9001fb21d 2011-08-20 kinaba: int _ = 886073030; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(5) c9001fb21d 2011-08-20 kinaba: string palette_[] = {"....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "....................", c9001fb21d 2011-08-20 kinaba: "...................."}; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = 10; c9001fb21d 2011-08-20 kinaba: int m = 10; c9001fb21d 2011-08-20 kinaba: int _ = 240076532; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: /* c9001fb21d 2011-08-20 kinaba: CASE(6) c9001fb21d 2011-08-20 kinaba: string palette_[] = ; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = ; c9001fb21d 2011-08-20 kinaba: int m = ; c9001fb21d 2011-08-20 kinaba: int _ = ; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: CASE(7) c9001fb21d 2011-08-20 kinaba: string palette_[] = ; c9001fb21d 2011-08-20 kinaba: vector <string> palette(palette_, palette_+sizeof(palette_)/sizeof(*palette_)); c9001fb21d 2011-08-20 kinaba: int n = ; c9001fb21d 2011-08-20 kinaba: int m = ; c9001fb21d 2011-08-20 kinaba: int _ = ; c9001fb21d 2011-08-20 kinaba: END c9001fb21d 2011-08-20 kinaba: */ c9001fb21d 2011-08-20 kinaba: } c9001fb21d 2011-08-20 kinaba: // END CUT HERE