茜茜的计算器时间限制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 71097取模的结果。示例示例 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 71097取模。本题的核心在于分析七段数码管数字在水平轴、竖直轴翻转下的对称性以及对称数字之间的镜像对应关系例如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 n1-in1−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^{h1}2h1种。因此额外贡献的竖直对称非横轴对称图形数为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^97}Ans4nextra(mod1097)使用快速幂计算幂次时间复杂度O ( log ⁡ n ) O(\log n)O(logn)可以轻松处理n ≤ 10 9 n \le 10^9n≤109。总结通过分析七段数码管数字在横轴和竖轴翻转下的对称性将问题分解为横轴对称和竖轴对称两类。横轴对称数量直接为4 n 4^n4n竖轴对称需要考虑位置对的自对称与镜像对并扣除与横轴对称重叠的部分。最终利用快速幂高效求解。代码简要说明qpow(a,b)快速幂函数用于计算a b m o d 10 9 7 a^b \bmod 10^97abmod1097。计算主答案r qpow(4,n)。额外贡献令h n / 2。若n为奇数extra 2 * (qpow(2,h)-1) * qpow(2,h) % mod。若n为偶数extra (qpow(2,h)-1) * qpow(2,h) % mod。输出输出(r extra) % mod。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llqpow(ll a,ll b){ll r1;while(b){if(b1)rr*a%mod;b1;aa*a%mod;}returnr;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;ll rqpow(4,n)%mod;ll hn/2;if(n1){r(r2*(qpow(2,h)-1)*qpow(2,h)%mod)%mod;}else{r(r(qpow(2,h)-1)*qpow(2,h)%mod)%mod;}coutrendl;return0;}