记录编号	392119	评测结果	AAAAAAAAAA
题目名称	[HEOI 2013]钙铁锌硒维生素	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	2.341 s
提交时间	2017-04-07 09:25:11	内存使用	0.92 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#define o3 __attribute__((optimize("O3")))

using namespace std;
const int MOD = 1e9+7;
const int MAXN = 300;
typedef long long ll;
typedef int Matrix[MAXN][MAXN];

int n;
Matrix A, B, C;

namespace NumberTheory {
	o3 int pow_mod( register int a, register int b ) {
	    register int c = 1;
		while(b) {
			if( b&1 ) c = (ll)c * a % MOD;
			a = (ll)a * a % MOD;
			b >>= 1;
		}
		return c;
	}
	o3 int inv( register int a ) {
		return pow_mod(a,MOD-2);
	}
}
using namespace NumberTheory;

namespace MatrixOP {
	o3 void read( Matrix A ) {
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				scanf( "%d", &A[i][j] );
	}
	o3 bool gauss_jordan( int A[MAXN][MAXN<<1], register int n, register int m ) {
		for( register int i = 0; i < n; ++i ) {
			register int r;
			for( r = i; r < n; ++r )
				if( A[r][i] ) break;
			if( r == n ) return false;
			if( r != i )
				for( register int j = i; j < m; ++j )
					swap( A[r][j], A[i][j] );
			register int iv = inv( A[i][i] );
			for( register int j = i; j < m; ++j )
				A[i][j] = (ll)A[i][j] * iv % MOD;
			for( register int j = 0; j < n; ++j )
				if( j != i && A[j][i] ) {
					register int tmp = MOD - A[j][i];
					for( register int k = i; k < m; ++k )
						A[j][k] = (A[j][k] + (ll)A[i][k] * tmp % MOD) % MOD;
				}
		}
		return true;
	}
	o3 bool inv( const Matrix A, Matrix B ) {
		int C[MAXN][MAXN<<1] = {0};
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				C[i][j] = A[i][j];
		for( register int i = 0; i < n; ++i )
			C[i][i+n] = 1;
		if( !gauss_jordan(C,n,n<<1) )
			return false;
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				B[i][j] = C[i][j+n];
		return true;
	}
	o3 void copy( const Matrix A, Matrix B ) {
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				B[i][j] = A[i][j];
	}
	o3 void mul( const Matrix A, const Matrix B2, Matrix C ) {
		Matrix tmp = {0}, B;
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				B[i][j] = B2[j][i];
		for( register int i = 0; i < n; ++i )
			for( register int j = 0; j < n; ++j )
				for( register int k = 0; k < n; ++k )
					tmp[i][j] = (tmp[i][j] + (ll)A[i][k] * B[j][k] % MOD) % MOD;
		copy(tmp,C);
	}
	o3 void trans( Matrix A ) {
		for( register int i = 0; i < n; ++i )
			for( register int j = i+1; j < n; ++j )
				swap(A[i][j], A[j][i]);
	}
	o3 void print( const Matrix A ) {
		for( register int i = 0; i < n; ++i ) {
			for( register int j = 0; j < n; ++j )
				printf( "%d ", A[i][j] );
			puts("");
		}
	}
}
using namespace MatrixOP;

namespace Hungarian {
	bool vis[MAXN];
	int lmatch[MAXN], rmatch[MAXN];
	o3 bool dfs1( register int u ) {
		for( register int v = 0; v < n; ++v ) {
			if( !C[u][v] || vis[v] ) continue;
			vis[v] = true;
			if( rmatch[v] == -1 || dfs1(rmatch[v]) ) {
				rmatch[v] = u;
				lmatch[u] = v;
				return true;
			}
		}
		return false;
	}
	o3 bool dfs2( register int u, register int s ) {
		for( register int v = 0; v < n; ++v ) {
			if( !C[u][v] || vis[v] ) continue;
			vis[v] = true;
			if( rmatch[v] == s || (rmatch[v] > s && dfs2(rmatch[v], s)) ) {
				rmatch[v] = u;
				lmatch[u] = v;
				return true;
			}
		}
		return false;
	}
	o3 bool solve() {
		memset( lmatch, -1, sizeof(lmatch) );
		memset( rmatch, -1, sizeof(rmatch) );
		// puts("ready for dfs1()");
		register int cnt = 0;
		for( register int i = 0; i < n; ++i )
			if( lmatch[i] == -1 ) {
				memset( vis, 0, sizeof(vis) );
				if( dfs1(i) ) ++cnt;
			}
		// puts("finished dfs1()");
		// for( int i = 0; i < n; ++i )
		// 	printf( "lmatch[%d] = %d\n", i, lmatch[i] );
		if( cnt != n ) return false;
		for( register int i = 0; i < n; ++i ) {
			memset( vis, 0, sizeof(vis) );
			dfs2(i,i);
			// for( int i = 0; i < n; ++i )
			// 	 printf( "lmatch[%d] = %d\n", i, lmatch[i] );
		}
		return true;
	}
}

o3 int main() {
	freopen( "ferrous.in", "r", stdin );
	freopen( "ferrous.out", "w", stdout );
	scanf( "%d", &n );
	read(A), read(B);
	if( !inv(A,C) ) {
		puts("NIE");
		return 0;
	}
	// print(C);
	mul(B,C,C);
	trans(C);
	// print(C);
	if( !Hungarian::solve() ) {
		puts("NIE");
		return 0;
	}
	puts("TAK");
	for( register int i = 0; i < n; ++i )
		printf( "%d\n", Hungarian::lmatch[i]+1 );
	return 0;
}