java 垒骰子
2024-09-07 01:43:04
垒骰子
赌圣atm晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。
经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥!
我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。
假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。 atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多,请输出模 10^9 + 7 的结果。
不要小看了 atm 的骰子数量哦~
「输入格式」
第一行两个整数 n m
n表示骰子数目
接下来 m 行,每行两个整数 a b ,表示 a 和 b 不能紧贴在一起。
「输出格式」
一行一个数,表示答案模 10^9 + 7 的结果。
「样例输入」
2 1
1 2
「样例输出」
544
「数据范围」
对于 30% 的数据:n <= 5
对于 60% 的数据:n <= 100
对于 100% 的数据:0 < n <= 10^9, m <= 36
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。
自己写的解法,用了dfs和回溯
import java.util.Scanner;
public class Main {
static int all = 0; //总数,没有算上4面的情况
static int[][] arr = new int[6][6]; //二维数组
static int s = 1;
public static int num(int a) { //判断对面的数
if(a>2) return a-3;
else return a+3;
}
public static void game(int a, int h, int r) { //从下到上,a是每一层下面骰子的数,s是判断到哪一层了,r是总层数
for(int i = 0; i<6; i++) { //整个game是核心算法
if(arr[a][i] == 1)
continue;
else {
if(h == r) {
all++;
}
else {
s++;
game(num(a), s, r);
s--;
}
}
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 0; i<6; i++) { //初始化数组
for(int j = 0; j<6; j++) {
arr[i][j] = 0;
}
}
for(int i = 0; i<m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
arr[a-1][b-1] = 1; //1表示互斥
arr[b-1][a-1] = 1;
}
for(int i = 0; i<6; i++) { //分六次,从第一层第一个骰子的数字开始,就是1-6
game(i, s, n-1);
}
System.out.print((all*(int)Math.pow(4,n)) % (int)(10e9+7));
}
}
网上还有另外的解法,矩阵快速幂,还有滚动数组。
最新文章
- 搭建一个简单的svn服务器
- [deviceone开发]-do_Dialog的基本使用示例
- 【bzoj3160】万径人踪灭 FFT
- javascript中字符串常用操作总结、JS字符串操作大全
- c++之路进阶——codevs4543(普通平衡树)
- nylg 小M的因子和
- hdu 4288 Coder
- BZOJ 3439 Kpm的MC密码
- 一种简单的权限管理ER图设计
- C#总结(3)
- DSP TMS320C6000基础学习(1)——介绍
- Python 函数基础、有序集合、文件操作(三)
- android studio没有浮现函数用法和属性说明?
- 关于MFC实时的视频处理
- PHP二维关联数组的遍历方式
- SpringMVC源码之Controller查找原理
- nodejs操作mysql常见错误
- 我的C#跨平台之旅(六):发布应用
- Linux系统中的文件权限
- WinForm读取指定的config文件的内容
热门文章
- 【Android多线程】异步任务AsyncTask类
- i.MX RT600之I2S外设介绍及应用
- UIImage点九图(让image不变形、只拉伸中间部分)
- 关于TXT文件中英文字母出现频率排序问题
- PAT T1017 The Best Peak Shape
- Mayor&#39;s posters-POJ2528 区间染色+离散化
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 网格系统实例:嵌套列
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 排版:设置浮动和偏移
- Uber为何会成为共享经济中全球市值最大的独角兽企业?
- 「HNOI2016」大数