Artifact Content
Not logged in

Artifact 033d37ff367d441d4deb57e1dad60d2b2f77d24b


#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;

template<typename T>
struct DP4
{
	int N1, N2, N3, N4;
	vector<T> data;
	DP4(int N1, int N2, int N3, int N4, const T& t = T())
		: N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3, int i4)
		{ return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
	void swap(DP4& rhs)
		{ data.swap(rhs.data); }
};

static const LL MODVAL = 1000000007;
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;
}
LL DIV(LL x, LL y) { return MUL(x, POW(y, MODVAL-2)); }
LL C(LL n, LL k) {
	k = min(n, n-k);
	LL v = 1;
	for(LL i=1; i<=k; ++i)
		v = DIV(MUL(v, n-i+1), i);
	return v;
}
LL FACT(LL n) {
	return n<=1 ? 1 : MUL(n, FACT(n-1));
}

class TwoSidedCards { public:
	int theCount(vector <int> taro, vector <int> hanako) 
	{
		int N = taro.size();
		vector<LL> loops;
		{
			vector<int> next(N);
			for(int i=0; i<N; ++i)
				next[taro[i]-1] = hanako[i]-1;

			vector<bool> used(N);
			for(int s=0; s<N; ++s)
				if( !used[s] ) {
					used[s] = true;

					LL looplen = 1;
					for(int v=next[s]; v!=s; v=next[v]) {
						used[v] = true;
						++looplen;
					}
					loops.push_back(looplen);
				}
		}

		return (int)solve(N, loops);
	}

	LL solve(int N, const vector<LL>& loops)
	{
		LL result = 1;

		LL rest = N;
		for(int i=0; i<loops.size(); ++i) {
			result = MUL(result, MUL(singleloop(loops[i]), C(rest,loops[i])));
			rest -= loops[i];
		}
		return result;
	}

	map< pair< pair<int,int>,pair<int,int> >, LL > memo;
	LL num_downtrig(int first, int last, int i, int n, int c)
	{
		if( i == n )
			return (last==1 && first==0 ? 1 : 0)==c ? 1 : 0;
		if( c < 0 )
			return 0;
		pair< pair<int,int>,pair<int,int> > key( make_pair(first,last), make_pair(i,c) );
		if( memo.count(key) )
			return memo[key];
		return memo[key] = ADD(
			num_downtrig(first, 0, i+1, n, c-(last==1)),
			num_downtrig(first, 1, i+1, n, c));
	}
	LL singleloop(int n)
	{
		if( n == 1 )
			return 1;
		LL fn = FACT(n);
		LL result = 0;
		memo.clear();
		for(int c=0; c<n; ++c)
		{
			LL z;
			if( c == 0 )
				z = num_downtrig(0, 0, 1, n, c);
			else
				z = ADD(
					num_downtrig(0, 0, 1, n, c),
					num_downtrig(1, 1, 1, n, c));
			result = ADD(result, DIV(MUL(z,fn), POW(2,c)));
		}
		return result;
	}
};

// 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(_, TwoSidedCards().theCount(taro, hanako));}
int main(){

CASE(0)
	int taro_[] = {1, 2, 3};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {1, 3, 2};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 12; 
END
CASE(1)
	int taro_[] = {1, 2, 3};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {1, 2, 3};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 6; 
END
CASE(2)
	int taro_[] = {1, 2};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {2, 1};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 4; 
END
CASE(3)
	int taro_[] = {5, 8, 1, 2, 3, 4, 6, 7};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {1, 2, 3, 4, 5, 6, 7, 8};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 2177280; 
END
CASE(4)
	int taro_[] = {41, 22, 17, 36, 26, 15, 10, 23, 33, 48, 49, 9, 34, 6, 21, 2, 46, 16, 25, 3, 24, 13, 40, 37, 35,
50, 44, 42, 31, 12, 29, 7, 43, 18, 30, 19, 45, 32, 39, 14, 8, 27, 1, 5, 38, 11, 4, 20, 47, 28};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {19, 6, 23, 35, 17, 7, 50, 2, 33, 36, 12, 31, 46, 21, 30, 13, 47, 22, 44, 4, 25, 24, 3, 15, 20,
48, 10, 28, 26, 18, 5, 45, 49, 16, 40, 42, 43, 14, 1, 37, 29, 8, 41, 38, 9, 11, 34, 32, 39, 27};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 529165844; 
END
CASE(5)
	int taro_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = -1; 
END
CASE(6)
int taro_[] = {1};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	  int hanako_[] = {1};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 1; 
END
CASE(7)
	int taro_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
	  vector <int> taro(taro_, taro_+sizeof(taro_)/sizeof(*taro_)); 
	int hanako_[] = {50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
	31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49};
	  vector <int> hanako(hanako_, hanako_+sizeof(hanako_)/sizeof(*hanako_)); 
	int _ = 1; 
END
}
// END CUT HERE