Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6218 --1.密码锁
6218: 1.密码锁
警告！
题目
状态
题解(1)
题目描述
小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 $0$ 到 $9$ 的数字。每个拨圈都是从 $0$ 到 $9$ 的循环，即 $9$ 拨动一个位置后可以变成 $0$ 或 $8$，  因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。 当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 $\tt{0\;0\;1\;1\;5}$ 转成 $\tt{1\;1\;1\;1\;5}$，但不会转成 $\tt{1\;2\;1\;1\;5}$。 时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 $n$ 个状态，注意这 $n$ 个状态都不是正确密码。 为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 $n$ 个状态。
输入
输入的第一行包含一个正整数 $n$，表示锁车后密码锁的状态数。 接下来 $n$ 行每行包含五个整数，表示一个密码锁的状态。
输出
输出一行包含一个整数，表示密码锁的这 $n$ 个状态按照给定的锁车方式能对应多少种正确密码。
样例输入输出
输入#1
复制
1 0 0 1 1 5
输出#1
复制
81
提示
**【样例 1 解释】** 一共有 $81$ 种可能的方案。 其中转动一个拨圈的方案有 $45$ 种，转动两个拨圈的方案有 $36$ 种。 对于所有测试数据有：$1 \leq n \leq 8$。 | 测试点 | $n\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1\sim 3$ | $1$ | 无 | | $4\sim 5$ | $2$ | 无 | | $6\sim 8$ | $8$ | A | | $9\sim 10$ | $8$ | 无 | 特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 $n$ 个状态。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及-
标签
点击显示
递交数
4
已通过
3
通过率
75%
时间限制
1 秒
内存限制
512 MB
来源
2023CSP-S
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和