蓝桥杯---垒骰子

赌圣atm晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥!我们先来规范一下骰子:1的对面是4,2的对面是5,3 的对面是 6。假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。由于方案数可能过多,请输出模 10^9+7的结果。不要小看了 atm的骰子数量哦~

[输入格式]
第一行两个整数 n m
 接下来 :n表示骰子数目
                m 行,每行两个整数ab,表示 a 和b 不能紧贴在一起。

[输出格式]
一行一个数,表示答案模 10^9+7的结果。

[样例输入]
2 1

1 2

[样例输出]
544

[数据范围]
对于 30% 的数据:n <= 5
对于 60% 的数据:n <= 100
对于 100% 的数据:0 <n <= 10^9,m <= 36

思路:暴力递归、动态规划

代码

public class _09垒骰子 {static int op[] = new int [7];private static int n;private static int m;private static final long MOO=1000000007;static void init(){op[1] = 4;op[4] = 1;op[2] = 5;op[5] = 2;op[3] = 6;op[6] = 3;}public static void main(String[] args) {init();Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();long conflict[][] = new long[6][6];for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {conflict[i][j] = 1;}}//        建立冲突矩阵for (int i = 0; i < m; i++) {int a = input.nextInt();int b = input.nextInt();conflict[op[a-1]][b-1] = 0;conflict[op[b-1]][a-1] = 0;}
//        求冲突矩阵的n-1次方long[][] nPow_n_1 = mPow(conflict,n-1);//            累加矩阵的每个元素long ans = 0;for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {ans = (ans + nPow_n_1[i][j])%MOO;}}
//            ans*4^nSystem.out.println(ans * power(4,n)%MOO);}private static long power(long i,int n){int ans = 1;while(n != 0){if((n & 1) ==1){ans *= (ans * i)%MOO;}i = i*i%MOO;n >>= 1;}return ans;}
//    矩阵的快速幂private static long[][] mPow(long[][] conflict,int n){long[][] e = new long[6][6];for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {if(i == j){e[i][j] = 1;}else{e[i][j] = 0;}}}while (n != 0){if((n & 1) == 1){e = mMul(e,conflict);}conflict = mMul(conflict,conflict);n >>= 1;}return e;}private static long[][] mMul(long[][] a ,long[][] b){long[][] ans = new long[6][6];for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {for (int k = 0; k < 6; k++) {ans[i][j] = (ans[i][j]+a[i][k] * b[k][j])%MOO;}}}return ans;}
}

 效果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/250456.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

arcgis javascript api4.x加载非公开或者私有的arcgis地图服务

需求&#xff1a; 加载arcgis没有公开或者私有的地图服务&#xff0c;同时还想实现加载时不弹出登录窗口 提示&#xff1a;​ 下述是针对独立的arcgis server&#xff0c;没有portal的应用场景&#xff1b; 如果有portal可以参考链接&#xff1a;https://mp.weixin.qq.com/s/W…

故障诊断 | 一文解决,CNN-LSTM卷积神经网络-长短期记忆神经网络组合模型的故障诊断(Matlab)

效果一览 文章概述 故障诊断 | 一文解决,CNN-LSTM卷积神经网络-长短期记忆神经网络组合模型的故障诊断(Matlab) 模型描述 CNN-LSTM模型是一种结合了卷积神经网络(Convolutional Neural Network)和长短期记忆神经网络(Long Short-Term Memory)的组合模型,常用于数据故障…

让MySQL和Redis数据保持一致的4种策略

1 前言 先阐明一下 MySQL 和 Redis 的关系&#xff1a;MySQL 是数据库&#xff0c;用来持久化数据&#xff0c;一定程度上保证数据的可靠性&#xff1b;Redis 是用来当缓存&#xff0c;用来提升数据访问的性能。 关于如何保证 MySQL 和 Redis 中的数据一致&#xff08;即缓存…

百无聊赖之JavaEE从入门到放弃(十八)其他常用类

目录 一.Math 类 二.Random 类 三.File类 四.枚举 一.Math 类 java.lang.Math 提供了一系列静态方法用于科学计算&#xff1b;常用方法如下&#xff1a; abs 绝对值 acos,asin,atan,cos,sin,tan 三角函数 sqrt 平方根 pow(double a, double b) a 的 b 次幂 max(double a,…

2401Idea用GradleKotlin编译Java控制台中文出乱码解决

解决方法 解决方法1 在项目 build.gradle.kts 文件中加入 tasks.withType<JavaCompile> {options.encoding "UTF-8" } tasks.withType<JavaExec> {systemProperty("file.encoding", "utf-8") }经测试, 只加 tasks.withType<…

后端——go系统学习笔记(不断更新中......)

数组 固定大小 初始化 arr1 : [3]int{1, 2, 3} arr2 : [...]int{1, 2, 3} var arr3 []int var arr4 [4]int切片 长度是动态的 初始化 arr[0:3] slice : []int{1,2,3} slice : make([]int, 10)len和cap len是获取切片、数组、字符串的长度——元素的个数cap是获取切片的容量—…

计算机视觉实战项目4(单目测距与测速+摔倒检测+目标检测+目标跟踪+姿态识别+车道线识别+车牌识别+无人机检测+A_路径规划+行人车辆计数+动物识别等)

基于YOLOv5的无人机视频检测与计数系统 摘要&#xff1a; 无人机技术的快速发展和广泛应用给社会带来了巨大的便利&#xff0c;但也带来了一系列的安全隐患。为了实现对无人机的有效管理和监控&#xff0c;本文提出了一种基于YOLOv5的无人机视频检测与计数系统。该系统通过使用…

C++类和对象(3)

目录 1.类的6个默认成员函数 2. 构造函数 2.1 概念 2.2 特性 3.析构函数 3.1 概念 3.2 特性 4. 拷贝构造函数 4.1 概念 4.2 特征 1.类的6个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任…

Web3生态系统:构建去中心化的数字社会

随着科技的飞速发展&#xff0c;我们正处在迈向数字未来的道路上&#xff0c;而Web3生态系统则成为这一变革的中心。不仅仅是技术的演进&#xff0c;Web3代表着对传统互联网体系的颠覆&#xff0c;致力于构建一个去中心化的数字社会。本文将深入探讨Web3的核心特征、对金融、社…

数据可视化 pycharts实现地理数据可视化(全球地图)

自用版 紧急整理一点可能要用的可视化代码&#xff0c;略粗糙 以后有机会再改 requirements&#xff1a; python3.6及以上pycharts1.9 数据格式为&#xff1a; 运行结果为&#xff1a; import pandas as pd from pyecharts.charts import Map, Timeline from pyecharts im…

C#读取和保存INI文件配置

在C#应用程序中&#xff0c;读取和保存配置文件是常见的任务&#xff0c;而INI文件是一种轻量级的配置文件格式。在以下代码中&#xff0c;我们将探讨如何使用C#创建一个窗体应用程序&#xff0c;并通过读取和保存INI文件配置来实现一些基本的功能。 创建IniHelper类 首先&…

Node需要了解的知识

Node能执行javascript的原因。 浏览器之所以能执行Javascript代码&#xff0c;因为内部含有v8引擎。Node.js基于v8引擎封装&#xff0c;因此可以执行javascript代码。Node.js环境没有DOM和BOM。DOM能访问HTML所有的节点对象&#xff0c;BOM是浏览器对象。但是node中提供了cons…

Arcgis10.3安装

所需软件地址 链接&#xff1a;https://pan.baidu.com/s/1aAykUDjkaXjdwFjDvAR83Q?pwdbs2i 提取码&#xff1a;bs2i 1、安装License Manager 点击License Manager.exe&#xff0c;默认下一步。 安装完&#xff0c;点击License Server Administrator&#xff0c;停止服务。…

时间序列预测 —— TCN模型

时间序列预测 —— TCN模型 卷积神经网络&#xff08;Convolutional Neural Network&#xff0c;CNN&#xff09;在图像处理等领域取得了显著的成就&#xff0c;一般认为在处理时序数据上不如RNN模型&#xff0c;而TCN&#xff08;Temporal Convolutional Network&#xff09;…

autojs简介与对抗

前言 最近发现现在大多安卓工具很多都是autojs和按键精灵等这些非常易于开发的工具来做黑灰产自动化工具&#xff0c;此帖也是由此做为出发点来展开说说这个autojs&#xff0c;我们如何去做对抗。由于笔者对这块也是刚了解学习不久而且这篇帖子也会说的很简单&#xff0c;有很…

【数据结构】认识数据结构 (通俗解释)

目录 1.认识数据结构 1.1 什么是数据结构 1.1.1 什么是数据&#xff1f; 1.1.2 什么是结构&#xff1f; 1.1.3 通俗比喻&#xff1a; 1.1.4 标准概念概念定义&#xff1a; 1.2为什么需要数据结构&#xff1f; 1.认识数据结构 1.1 什么是数据结构 数据结构是由"数…

【Springcloud篇】学习笔记二(四至六章):Eureka、Zookeeper、Consul

第四章_Eureka服务注册与发现 1.Eureka基础知识 1.1Eureka工作流程-服务注册 1.2Eureka两大组件 2.单机Eureka构建步骤 IDEA生成EurekaServer端服务注册中心&#xff0c;类似于物业公司 EurekaClient端cloud-provider-payment8081将注册进EurekaServer成为服务提供者provide…

【QT】贪吃蛇小游戏 -- 童年回忆

成品展示 项目分析&#xff1a; &#x1f40d;基本元素如下 &#x1f40d;小蛇的设计&#xff0c;初始大小蛇头占一个方块&#xff0c;蛇身占两个方块。 &#x1f40d;关于小蛇的移动&#xff0c;采用蛇头前进方向增加一个方块&#xff0c;蛇尾减掉一个方块的实现方法。 &#…

yum命令下载出现Failed to synchronize cache for repo ‘AppStream‘, ignoring this repo.

修改下面的配置文件 问题&#xff1a; cd /etc/yum.repos.d 修改下面四个文件 vim CentOS-Base.repo vim CentOS-AppStream.repo vim CentOS-Extras.repo vim CentOS-PowerTools.repo测试yum是否正常 yum -y install wget

Linux 高并发服务器

多进程并发服务器 使用多进程并发服务器时要考虑以下几点&#xff1a; 父进程最大文件描述个数(父进程中需要close关闭accept返回的新文件描述符)系统内创建进程个数(与内存大小相关)进程创建过多是否降低整体服务性能(进程调度) server /* server.c */ #include <stdio…