2016西电校赛网络赛 Problem F 方格填数

2019-04-14 18:29发布

站内文章 / 模拟电子
14986 0 989

Problem F 6 方格填数

问题描述

万神在纸上画了一个 3 × 3 的表格,希望把 1 · · · 9 填入表格中,每个数只填
一次。然而,这样会有 9! = 362880 种不同的填数方案。万神觉得方案太多了,
于是又写下 9 个正整数 a 1 · · · a 9 ,并规定填数方案合法的充要条件是:对于表格
中任意一对相邻的数 x, y,必须满足 a x 和 a y 互质,即它们的最大公约数是 1。
那么,还有多少种合法的填数方案呢?
相邻定义为两个数所在的格子有公共边。

输入格式

输入包含多组数据(最多 100 组),请处理到文件结束。
每组数据只有 1 行,包含 9 个正整数 a 1 · · · a 9 ,用空格分割。
保证 1 ≤ a i ≤ 10 9 。

输出格式

对于每组数据输出 1 行,包含 1 个整数,即合法的填数方案的个数。

输入样例

1 1 1 1 1 1 1 1 1
2 2 2 4 4 4 6 6 6
2 2 2 2 2 3 3 3 3

输出样例

362880
0
2880

样例解释

对于第一组样例,所有方案都是合法的。
对于第二组样例,所有方案都是不合法的。
对于第三组样例,必须把 1 · · · 5 放在表格的两条对角线上,6 · · · 9 放在其他
4 个格子上,所以有 5! × 4! = 2880 种方案。

思路：

深搜么！！～～～～
/************************************************************************* > File Name: f.cpp > Author: dulun > Mail: dulun@xiyoulinux.org > Created Time: 2016年04月20日 星期三 14时45分24秒 ************************************************************************/ #include #include #include #include #include #define LL long long using namespace std; const int N = 50086; int ans = 0; bool over = 0; int a[10]; int now[10]; bool v[10]; int gcd(int a, int b) { return a%b==0 ? b : gcd(b, a%b); } bool check(int cur, int k) { if(cur == 0) return true; if(cur - 3 >= 0) { if(gcd(now[cur-3], k) != 1) return false; } if(cur % 3 != 0 ) { if(gcd(now[cur-1], k) != 1) return false; } return true; } void dfs(int cur) { if(cur == 9) { ans++; return; } for(int i = 0; i < 9; i++) { if(v[i] == true) continue; if(check(cur, a[i]) == true) { v[i] = 1; now[cur] = a[i]; dfs(cur+1); v[i] = 0; } } } int main() { while(~scanf("%d", &a[0])) { ans = 0; for(int i = 1; i < 9; i++) { scanf("%d", &a[i]); } dfs(0); if(over == 1) { printf("0 "); continue; } printf("%d ", ans); } return 0; }

热门文章