第六届-蓝桥杯省赛-垒筛子

2024-08-23 14:38
文章标签 蓝桥 省赛 第六届 筛子

本文主要是介绍第六届-蓝桥杯省赛-垒筛子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

9、垒骰子

 

赌圣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,否则按无效代码处理。


解题思路:

对于100%的数据普速算法行不通必然会超时;使用快速幂的思想切之;

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 1000000007
typedef long long LL;
int dp[11][11][2];
int ans[11][11];
int che[11][11];
int n,m;
void work1(int k){for(int dd = 1;dd<=6;dd++)for(int uu = 1;uu<=6;uu++)dp[dd][uu][k%2] = 0;for(int du = 1;du<=6;du++) {for(int ud = 1;ud<=6;ud++) {if(che[du][ud]==1) continue;for(int dd = 1;dd<=6;dd++) {for(int uu = 1;uu<=6;uu++) {int t = (LL)dp[ud][uu][(k+1)%2]*4%MOD*4%MOD;dp[dd][uu][k%2] = ((LL)dp[dd][uu][k%2]+(LL)t*dp[dd][du][(k+1)%2]%MOD)%MOD;}}}}
}
void work2(int k){int tem[11][11];memset(tem,0,sizeof(tem));for(int du = 1;du<=6;du++){for(int ud = 1;ud<=6;ud++){if(che[du][ud]==1) continue;for(int dd = 1;dd<=6;dd++){for(int uu = 1;uu<=6;uu++){int t = (LL)ans[ud][uu]%MOD*4%MOD*4%MOD;tem[dd][uu] = ((LL)tem[dd][uu]+(LL)t*dp[dd][du][k%2]%MOD)%MOD;}}}}for(int up = 1;up<=6;up++)for(int dow = 1;dow<=6;dow++)ans[dow][up] = tem[dow][up];
}
void solve(){int k = 0;while(n){if(n&1) work2(k);work1(k+1);n>>=1;}
}
void init() {memset(che,0,sizeof(che));memset(ans,0,sizeof(ans));memset(dp,0,sizeof(dp));ans[1][4] = ans[4][1] = dp[1][4][0] = dp[4][1][0] = 1;ans[2][5] = ans[5][2] = dp[2][5][0] = dp[5][2][0] = 1;ans[3][6] = ans[6][3] = dp[3][6][0] = dp[6][3][0] = 1;
}
int main(){int x,y;while(~scanf("%d%d",&n,&m)){init();for(int i = 1;i<=m;i++){scanf("%d%d",&x,&y);che[y][x] = che[x][y] = 1;}solve();int res = 0;for(int up = 1;up<=6;up++)for(int dow = 1;dow<=6;dow++)res = (res + ans[dow][up])%MOD;printf("%d\n",res);}return 0;
}



这篇关于第六届-蓝桥杯省赛-垒筛子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099671

相关文章

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读,可以点击《Scratch蓝桥杯历年真题》并订阅合集,查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕,编程题一共有5题,分别如下: 猪八戒落地 游乐场 画西瓜 找不同 消

【蓝桥杯嵌入式(一)程序框架和调度器】

蓝桥杯嵌入式(一)程序框架和调度器 序、代码命名规则零、STM32和8051⼀、软件及环境安装⼆、⼯程框架搭建1.时钟配置2、SYS配置3、⼯程配置4、NVIC配置5.、Keil配置 三、系统初始化四、任务调度器 链接: 视频出处 序、代码命名规则 以下是一些常见的举例 零、STM32和8051 链接: 8位和32位单片机最本质区别 ⼀、软件及环境安装

【蓝桥杯嵌入式(二)Led、Key、Lcd】

蓝桥杯嵌入式(二)Led、Key、Lcd 五、Led模块1.原理图配置2. 知识点3.底层代码 六、Key模块1.原理图配置2.知识点3.底层代码底层代码(四⾏代码版本)底层代码(状态机版本) 七、LCD模块1.原理图配置2.知识点底层代码 五、Led模块 1.原理图配置 2. 知识点 链接: 上拉电阻的通俗解释 链接: 单⽚机怎么输出⾼电平!推挽输出和开

蓝桥杯:整数删除

// 蓝桥杯整数删除.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include<stdio.h>#define MAX 100void findmin(int a[],int n,int& pos){int min=a[0];pos=0;//pos=0我开始忘了,特别注意

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序,角色会说( )? A、29     B、31     C、33     D、35 正确答案:C 答案解析: 重复执行直到m>n不成立,即重复执行直到m<=n。所有当m小于或者 等于n时,循环结束。循环过程中变量m与变量n的变化如下表: 通过上述表格可知,循环到第五次循环结束。m的值为14,n的值为19

第八届蓝桥杯 最大公共子串(动态规划)

标题:最大公共子串 最大公共子串长度问题就是: 求两个串的所有子串中能够匹配上的最大长度是多少。 比如:"abcdkkk" 和 "baabcdadabc", 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。 请分析该解法的思路,并补全划线部分缺失的代码。 #include <stdio.h

蓝桥杯第八届 方格分割(dfs)

标题:方格分割6x6的方格,沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图:p1.png, p2.png, p3.png 就是可行的分割法。试计算:包括这3种分法在内,一共有多少种不同的分割方法。注意:旋转对称的属于同一种分割法。请提交该整数,不要填写任何多余的内容或说明文字。   观察可得他是一个中心对称图形,我们只需要搜索它的对称线即可。我们可以把对称线抽象为从(

蓝桥杯备赛day02:递推

斐波那契数列 #include <bits/stdc++.h>using namespace std;int main(){int n;cin>>n;int dp[n+1];dp[1]=1;dp[2]=1;for(int i = 3;i <= n;i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[n];return 0;} n = int(input())