USACO Postal Vans 解题报告

这道题我是用偷懒的方法做的。在topcoder论坛上面看到大名鼎鼎的msg555也是用的这种方法，于是我就放心了。首先，用DFS跑n比较小的情况，可以跑到n=10，如果你足够耐心的话，也可以得到更多结果。于是就有了下面的结果，对n=1~11:int arr[] = {0, 2, 4, 12, 28, 74, 184, 472, 1192, 3034, 7692}; 在这之后就是找规律了。https://oeis.org/（我是给系统发邮件）和http://www.wolframalpha.com/网站都可以得到生成函数，后者还可以以极短的时间算出来后续的序列（很好奇是如何做到的，还是高精度运算）。由于数学功底已经不如之前了，不知道如何从生成函数导出递推公式。但知道有递推公式的存在，找到规律还是比较简单的。

我们有:a[n] = 2 * a[n - 1] + 2 * a[n - 2] - 2 * a[n - 3] + a[n - 4]

之后就是如何根据这个递推式导出结果，及超过int的范围怎么办（观察增长速度，突破32位int是很快的事情）。

我用的是最naive的方法，写了个1000位的加法和减法，然后把乘法当做多次加法（或减法）。于是就有了下面的解法：

USER: chen chen [thestor1]
TASK: vans
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.008 secs, 3504 KB]
   Test 2: TEST OK [0.008 secs, 3504 KB]
   Test 3: TEST OK [0.003 secs, 3504 KB]
   Test 4: TEST OK [0.008 secs, 3504 KB]
   Test 5: TEST OK [0.005 secs, 3504 KB]
   Test 6: TEST OK [0.008 secs, 3504 KB]
   Test 7: TEST OK [0.005 secs, 3504 KB]
   Test 8: TEST OK [0.016 secs, 3504 KB]
   Test 9: TEST OK [0.032 secs, 3504 KB]
   Test 10: TEST OK [0.043 secs, 3504 KB]
   Test 11: TEST OK [0.057 secs, 3504 KB]

All tests OK.

/* 
ID: thestor1 
LANG: C++ 
TASK: vans 
*/
#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;

const int MAXN = 1000;

int N;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

bool isIn(int r, int c)
{
	return 0 <= r && r < 4 && 0 <= c && c < N; 
}

vector<pair<int, int> > neighbors(int r, int c)
{
	vector<pair<int, int> > nbs;
	int nr, nc;
	for (int d = 0; d < 4; ++d)
	{
		nr = r + dx[d], nc = c + dy[d];
		if (isIn(nr, nc))
		{
			nbs.push_back(make_pair(nr, nc));
		}
	}
	return nbs;
}

void DFS(vector<vector<bool> > &visited, int r, int c, int cnt, int &total)
{
	if (visited[0][0])
	{
		if (cnt == 4 * N)
		{
			total++;
		}
		return;	
	}

	vector<pair<int, int> > nbs = neighbors(r, c);
	int nr, nc;
	for (int i = 0; i < nbs.size(); ++i)
	{
		nr = nbs[i].first, nc = nbs[i].second;
		if (!visited[nr][nc])
		{
			visited[nr][nc] = true;
			DFS(visited, nr, nc, cnt + 1, total);
			visited[nr][nc] = false;
		}
	}
}

void zero(std::vector<int> &num)
{
	for (int i = 0; i < num.size(); ++i)
	{
		num[i] = 0;
	}
}

void assign(std::vector<int> &lhs, std::vector<int> &rhs)
{
	assert (lhs.size() == rhs.size());
	for (int i = 0; i < lhs.size(); ++i)
	{
		lhs[i] = rhs[i];
	}
}

void add(std::vector<int> &lhs, std::vector<int> &rhs)
{
	int carry = 0, result;
	for (int i = lhs.size() - 1; i >= 0; --i)
	{
		result = lhs[i] + rhs[i] + carry;
		lhs[i] = result % 10;
		carry = result / 10;
	}
	assert(carry == 0);
}

void sub(std::vector<int> &lhs, std::vector<int> &rhs)
{
	int borrow = 0, result;
	for (int i = lhs.size() - 1; i >= 0; --i)
	{
		result = lhs[i] - rhs[i] - borrow;
		if (result < 0)
		{
			borrow = 1;
			lhs[i] = result + 10;
		}
		else
		{
			borrow = 0;
			lhs[i] = result;
		}
	}
	assert (borrow == 0);
}

void print(const std::vector<int> &lhs)
{
	int begin = 0;
	while (begin < MAXN && lhs[begin] == 0)
	{
		begin++;
	}
	
	for (int i = begin; i < lhs.size(); ++i)
	{
		cout << lhs[i];
	}
	cout << endl;
}

int main()
{
	ifstream fin("vans.in");
	fin >> N;
	fin.close();
	if (N <= 4)
	{
		int arr[] = {0, 2, 4, 12, 28, 74, 184, 472, 1192, 3034, 7692};
		ofstream fout("vans.out");
		fout << arr[N - 1] << endl;
		fout.close();
		return 0;
	}
	// vector<vector<bool> > visited(4, vector<bool>(N, false));
	// int total = 0;
	// DFS(visited, 0, 0, 0, total);
	// a[n] = 2 * a[n - 1] + 2 * a[n - 2] - 2 * a[n - 3] + a[n - 4]
	
	vector<vector<int> > a(5, vector<int>(MAXN, 0));

	// a[0]

	a[1][MAXN - 1] = 2;
	a[2][MAXN - 1] = 4;
	
	a[3][MAXN - 2] = 1;
	a[3][MAXN - 1] = 2;

	int a0 = 0, a1 = 1, a2 = 2, a3 = 3;

	
	for (int i = 4; i < N; ++i)
	{
		a0 = i % 4, a1 = (a0 + 1) % 4, a2 = (a1 + 1) % 4, a3 = (a2 + 1) % 4;
		zero(a[4]);
		// cout << "[debug]0" << endl;
		// print(a[4]);

		add(a[4], a[a3]);
		// cout << "[debug]1" << endl;
		// print(a[4]);

		add(a[4], a[a3]);
		// cout << "[debug]2" << endl;
		// print(a[4]);

		add(a[4], a[a2]);
		// cout << "[debug]3" << endl;
		// print(a[4]);

		add(a[4], a[a2]);
		// cout << "[debug]4" << endl;
		// print(a[4]);

		sub(a[4], a[a1]);
		// cout << "[debug]5" << endl;
		// print(a[4]);

		sub(a[4], a[a1]);
		// cout << "[debug]6" << endl;
		// print(a[4]);

		add(a[4], a[a0]);
		// cout << "[debug]7" << endl;
		// print(a[4]);

		assign(a[a0], a[4]);
	}

	ofstream fout("vans.out");
	
	int begin = 0;
	while (begin < MAXN && a[4][begin] == 0)
	{
		begin++;
	}
	
	for (int i = begin; i < a[4].size(); ++i)
	{
		fout << a[4][i];
	}
	fout << endl;
	
	fout.close();

	return 0;  
}