茜茜的计算器【牛客tracker 每日一题】

茜茜的计算器

时间限制：1 秒
空间限制：256 MB

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

茜茜有一个计算器，这个计算器在显示数字的时候会把所有的前导0 00都显示出来。

在这个计算器上，0 ∼ 9 0 \sim 90∼9分别被显示为下图中的七段数码管样式：

即，当这个计算器显示屏有10 1010位时，让它显示数字123456 123456123456则会显示为：

00000123456

茜茜发现，这个计算器有时候显示的数字是一个轴对称图形，如"80808"。

（"80808"的对称轴可以为横轴，也可以为纵轴。而有些数字可能只以横轴或纵轴中的一个为对称轴，但这样的仍然是轴对称图形。）

请问，如果这个计算器显示的数有n nn位时，它能显示的数字中有多少种不同的轴对称图形？

输入描述

读入一个正整数n nn。

数据范围：1 ≤ n ≤ 10 9 1 \le n \le 10^91≤n≤109。

输出描述

输出一个正整数，表示n nn位的计算器所能显示的数字中，有多少种不同的轴对称图形。

由于答案可能很大，输出答案对10 9 + 7 10^9 + 7109+7取模的结果。

示例

示例 1

输入：

2

输出：

18

说明：

有18 1818种不同的轴对称图形，分别为：

00, 01, 03, 08, 10, 11, 13, 18, 25, 30, 31, 33, 38, 52, 80, 81, 83, 88,

数据范围与提示

• 1 ≤ n ≤ 10 9 1 \le n \le 10^91≤n≤109
• 答案对10 9 + 7 10^9 + 7109+7取模。
• 本题的核心在于分析七段数码管数字在水平轴、竖直轴翻转下的对称性，以及对称数字之间的镜像对应关系（例如2 22与5 55在某种翻转下可相互映射），进而推导出n nn位数字串中轴对称图形的计数公式。

解题思路

本题是组合计数 + 轴对称图形分类问题。需要统计所有n nn位数字串中，在七段数码管显示下构成轴对称图形（关于横轴或纵轴）的个数。由于两种对称轴的条件不同，可分别计数后用容斥合并，避免重复。

1. 数字的对称性分析

七段数码管中各个数字的对称性质如下（可由样例和图形推导）：

• 水平轴（横轴）对称：上下翻转后图形不变的数字有0 , 1 , 3 , 8 0,1,3,80,1,3,8，共4 44个。因此任意由这四个数字组成的n nn位串都关于横轴对称。故横轴对称图形数量为：
  4 n 4^n4n

• 竖直轴（纵轴）对称：左右翻转后图形不变的数字有0 , 8 0,80,8，共2 22个。此外，2 22和5 55左右翻转互为镜像，可以配对使用。
  在竖直轴对称中，位置会整体左右颠倒，因此必须满足：

  • 若n nn为偶数，所有n / 2 n/2n/2对位置（第i ii位与第n + 1 − i n+1-in+1−i位）必须满足：要么两边都是同一个竖直自对称数字（0 00或8 88），要么两边是镜像对2 22和5 55（左边2 22右边5 55或左边5 55右边2 22）。
  • 若n nn为奇数，最中间一位必须是竖直自对称数字（0 00或8 88），两侧位置对规则同上。

2. 竖直对称图形计数

设h = ⌊ n / 2 ⌋ h = \lfloor n/2 \rfloorh=⌊n/2⌋（位置对的数量）。

• 每个位置对有4 44种选择：
  • 自对称：00 0000或88 8888，共2 22种；
  • 镜像对：25 2525或52 5252，共2 22种。
• 若n nn为偶数，竖直对称串总数为：
  V even = 4 h V_{\text{even}} = 4^hVeven​=4h
• 若n nn为奇数，中间位有2 22种选择，故：
  V odd = 2 × 4 h V_{\text{odd}} = 2 \times 4^hVodd​=2×4h

但这些竖直对称串中，有一部分全由0 00和8 88组成，它们同时也是横轴对称图形（因为0 , 8 0,80,8也在横轴对称数字集合中）。为避免重复计数，需要减去这部分。

• 竖直对称且横轴对称的数量：
  • n nn偶数：每个位置对必须选自对称数字，共2 h 2^h2h种。
  • n nn奇数：中间位2 22种，每个位置对2 22种，共2 h + 1 2^{h+1}2h+1种。

因此，额外贡献的竖直对称（非横轴对称）图形数为：
extra = { ( 2 h − 1 ) × 2 h , n 为偶数 2 × ( 2 h − 1 ) × 2 h , n 为奇数 \text{extra} = \begin{cases} (2^h-1)\times 2^h, & n \text{ 为偶数} \\[4pt] 2\times(2^h-1)\times 2^h, & n \text{ 为奇数} \end{cases}extra={(2h−1)×2h,2×(2h−1)×2h,​n为偶数n为奇数​

3. 最终答案

总数为横轴对称图形数加上额外竖直对称图形数：
Ans = 4 n + extra ( m o d 10 9 + 7 ) \text{Ans} = 4^n + \text{extra} \pmod{10^9+7}Ans=4n+extra(mod109+7)
使用快速幂计算幂次，时间复杂度O ( log ⁡ n ) O(\log n)O(logn)，可以轻松处理n ≤ 10 9 n \le 10^9n≤109。

总结

通过分析七段数码管数字在横轴和竖轴翻转下的对称性，将问题分解为横轴对称和竖轴对称两类。横轴对称数量直接为4 n 4^n4n；竖轴对称需要考虑位置对的自对称与镜像对，并扣除与横轴对称重叠的部分。最终利用快速幂高效求解。

代码简要说明

1. qpow(a,b)：快速幂函数，用于计算a b m o d 10 9 + 7 a^b \bmod 10^9+7abmod109+7。
2. 计算主答案：r = qpow(4,n)。
3. 额外贡献：
   • 令h = n / 2。
   • 若n为奇数：extra = 2 * (qpow(2,h)-1) * qpow(2,h) % mod。
   • 若n为偶数：extra = (qpow(2,h)-1) * qpow(2,h) % mod。
4. 输出：输出(r + extra) % mod。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llqpow(ll a,ll b){ll r=1;while(b){if(b&1)r=r*a%mod;b>>=1;a=a*a%mod;}returnr;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;ll r=qpow(4,n)%mod;ll h=n/2;if(n&1){r=(r+2*(qpow(2,h)-1)*qpow(2,h)%mod)%mod;}else{r=(r+(qpow(2,h)-1)*qpow(2,h)%mod)%mod;}cout<<r<<endl;return0;}