USACO All Latin Squares解題レポート

/*
 ID: thestor1
 LANG: C++
 TASK: latin
 */
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>

using namespace std;

void DFS(int r, int c, const int N, unsigned long long int &cnt, vector<vector<bool> > &appearedrow, vector<vector<bool> > &appearedcol, vector<int> &sumrow);

void printSquare(vector<vector<int> > &square)
{
	cout << "[debug]square:" << endl;
	for (int i = 0; i < square.size(); ++i)
	{
		for (int j = 0; j < square[i].size(); ++j)
		{
			cout << square[i][j];
		}
		cout << endl;
	}
}

void DFS(int r, int c, const int N, unsigned long long int &cnt, vector<vector<bool> > &appearedrow, vector<vector<bool> > &appearedcol, vector<int> &sumrow)
{
	// cout << "[debug][DFS]r: " << r << ", c: " << c << endl;
	// printSquare(square);

	if (r == N - 1)
	{
		// cout << "[debug]" << cnt << endl;
		cnt++;
		return;
	}

	int num;
	if (c == N - 1)
	{
		num = N * (N - 1) / 2 - sumrow[r];
		if (!appearedcol[num][c])
		{
			appearedcol[num][c] = true;
			DFS(r + 1, 1, N, cnt, appearedrow, appearedcol, sumrow);
			appearedcol[num][c] = false;
			// fill(r, c, num, N, cnt, appearedrow, appearedcol, sumrow);
		}
	}
	else
	{
		for (int num = 0; num < N; ++num)
		{
			if (!appearedrow[num][r] && !appearedcol[num][c])
			{
				appearedrow[num][r] = true;
				appearedcol[num][c] = true;
				sumrow[r] += num;
				DFS(r, c + 1, N, cnt, appearedrow, appearedcol, sumrow);
				sumrow[r] -= num;
				appearedrow[num][r] = false;
				appearedcol[num][c] = false;
			}
		}
	}
}

int main()
{
	ifstream fin("latin.in");
	int N;
	fin >> N;
	fin.close();


	if (N == 2)
	{
		ofstream fout("latin.out");
		fout << 1 << endl;
		fout.close();
		return 0;
	}

	// if (N == 7)
	// {
	// 	ofstream fout("latin.out");
	// 	fout << 12198297600 << endl;
	// 	fout.close();
	// 	return 0;
	// }
	
	// vector<vector<int> > square(N, vector<int>(N, 0));
	vector<vector<bool> > appearedrow(N, vector<bool>(N, false));
	vector<vector<bool> > appearedcol(N, vector<bool>(N, false));
	vector<int> sumrow(N, 0);
	// vector<int> sumcol(N, 0);
	
	for (int i = 0; i < N; ++i)
	{
		// square[0][i] = i;
		appearedrow[i][0] = true;
		appearedcol[i][i] = true;
		sumrow[0] += i;
		// sumcol[i] += i;
	}

	for (int i = 0; i < N; ++i)
	{
		// square[i][0] = i;
		appearedrow[i][i] = true;
		appearedcol[i][0] = true;
		sumrow[i] += i;
		// sumcol[0] += i;
	}

	unsigned long long int cnt = 0;

	// square[1][1] = 0;
	appearedrow[0][1] = true;
	appearedcol[0][1] = true;
	sumrow[1] += 0;
	unsigned long long int cnt1 = 0;
	DFS(1, 2, N, cnt1, appearedrow, appearedcol, sumrow);
	cnt += cnt1;

	// square[1][1] = 2;
	appearedrow[0][1] = false;
	appearedcol[0][1] = false;
	appearedrow[2][1] = true;
	appearedcol[2][1] = true;
	sumrow[1] -= 0;
	sumrow[1] += 2;
	
	cnt1 = 0;
	DFS(1, 2, N, cnt1, appearedrow, appearedcol, sumrow);
	cnt += cnt1 * (N - 2);

	for (int i = N - 1; i > 1; --i)
	{
		cnt *= i;
	}

	ofstream fout("latin.out");
	fout << cnt << endl;
	fout.close();
	return 0;  
}