Robbers' watch [Codeforces 359 : Div1 A, Div2 C]

問題

http://codeforces.com/contest/686/problem/C

1日がn時間、1時間がm分とする。
このとき、0～n-1時0～m-1分を7を法として表示する時計がある。
この時計の出目のうち、数が全て異なる組合せは何通りか。

1 <= n,m <= 10^9

思考の流れ

1. 解法が全然思いつかない時は全探索を考えよう

• 0時0分～順番に列挙して数える
• 制限的に無理そう
• 全列挙をまとめ上げて計算量を落とす or 別の数え上げ方

2. 今回は「全ての数が異なる」＋「7が法」ということで状態数がかなり減ってる

• 時計の出目を全列挙し、それが0時0分～n-1時m-1分の間にあるかを判定
• 7!は3000くらいなので楽勝

解法

順列（aPbで数え上げるようなやつ）の全列挙はdfsでやると便利

int n, m;
//-----------------------------------------------------------------
int digits(int x) {
	if (x == 0) return 1;

	int ret = 0;
	while (0 < x) {
		ret++;
		x /= 7;
	}
	return ret;
}
//-----------------------------------------------------------------
int n_len, m_len, len;
int vec[7] = { 0, 1, 2, 3, 4, 5, 6 };

int dfs(int d) {
	if (d == len) {
		int nn = 0;
		rep(i, 0, n_len) nn = nn * 7 + vec[i];

		int mm = 0;
		rep(i, n_len, len) mm = mm * 7 + vec[i];

		if (nn < n && mm < m)
			return 1;
		else
			return 0;
	}

	int ret = 0;
	rep(i, d, 7) {
		swap(vec[d], vec[i]);
		ret += dfs(d + 1);
		swap(vec[d], vec[i]);
	}
	return ret;
}
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &n, &m);
	
	n_len = digits(n - 1);
	m_len = digits(m - 1);
	len = n_len + m_len;

	int ans = 0;
	if (n_len + m_len <= 7) ans = dfs(0);
	printf("%d\n", ans);
}