Problem Description
A seven segment display, or seven segment indicator, is a form of electronic display device for displaying decimal numerals that is an alternative to the more complex dot matrix displays. Seven segment displays are widely used in digital clocks, electronic meters, basic calculators, and other electronic devices that display numerical information.
Edward, a student in Marjar University, is studying the course "Logic and Computer Design Fundamentals" this semester. He bought an eight-digit seven segment display component to make a hexadecimal counter for his course project.
In order to display a hexadecimal number, the seven segment display component needs to consume some electrical energy. The total energy cost for display a hexadecimal number on the component is the sum of the energy cost for displaying each digit of the number. Edward found the following table on the Internet, which describes the energy cost for display each kind of digit.
For example, in order to display the hexadecimal number "$5A8BEF67$" on the component for one second, $5 + 6 + 7 + 5 + 5 + 4 + 6 + 3 = 41$ units of energy will be consumed.
Edward's hexadecimal counter works as follows:
- The counter will only work for n seconds. After $n$ seconds the counter will stop displaying.
- At the beginning of the 1st second, the counter will begin to display a previously configured eight-digit hexadecimal number $m$.
- At the end of the $i$-th second ($1$ $≤$ $i$ $<$ $n$), the number displayed will be increased by $1$. If the number displayed will be larger than the hexadecimal number "$FFFFFFFF$" after increasing, the counter will set the number to $0$ and continue displaying.
Input
There are multiple test cases. The first line of input contains an integer $T$ $(1 ≤ T ≤ 10^5)$, indicating the number of test cases. For each test case:
The first and only line contains an integer $n (1 ≤ n ≤ 10^9)$ and a capitalized eight-digit hexadecimal number $m (00000000 ≤ m ≤ FFFFFFFF)$, their meanings are described above.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case output one line, indicating the total units of energy consumed by the eight-digit seven segment display component.
Sample Input
3
5 89ABCDEF
3 FFFFFFFF
7 00000000Sample Output
208
124
327Hint
For the first test case, the counter will display $5$ hexadecimal numbers $(89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3)$ in $5$ seconds. The total units of energy cost is $$\begin{align}(7 + 6 + 6 + 5 + 4 + 5 + 5 + 4) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 6) \\ + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 2) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) \\ + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) = 208\end{align}$$.
For the second test case, the counter will display $3$ hexadecimal numbers $(FFFFFFFF, 00000000, 00000001)$ in $3$ seconds. The total units of energy cost is $$\begin{align}(4 + 4 + 4 + 4 + 4 + 4 + 4 + 4) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 6) \\ + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 2) = 124\end{align}$$.
Problem Link
[button color="success" url="https://vjudge.net/problem/ZOJ-3962" outline="default" target="_blank"]vjudge_ZOJ_3962_Seven Segment Display[/button]
Thoughts
数位DP，有点像打表的感觉，但又没那么容易，首先判断一下$n$秒以后有没有超过$0xffffffff$如果超了，那么结果就等于
$\begin{align}(0xffffffff的权值-((初始值-1的权值)- (初始值加上n-1秒-(0xffffffff+1)后的权值)))\end{align}$若没超过那就好算了$(初始值+n-1的权值-初始值-1的权值)$没看懂的可以自己画个图试一下，就是如果超过了$0xffffffff$就求补集否则，直接求。
Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef long long LL;
int cost[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4};
const LL mod =(LL)0xffffffff+1;
int a[20]; //存储16进制数字（字母转化为数字）
LL dp[20][1005]; //数位dp，名字不用管啦，看代码就知道了
LL change(char *str) //将字符串组合成一个16进制的数
{
LL tmp=0;
for(int i=0;i<8;i++)
{
if(str[i]>='0' && str[i]<='9')
tmp=tmp*16+str[i]-'0';
else
tmp=tmp*16+str[i]-'A'+10;
}
return tmp;
}
LL dfs(int pos, LL sum,int limit)
{
if(pos<0) //若最低位已经计算完成
return sum;
if(!limit && dp[pos][sum]!=-1) //效率优化，极大极大的优化的
return dp[pos][sum];
int up=limit ? a[pos]:15;
LL tmp=0;
for(int i=0;i<=up;i++) //计算此位上所有可能的数字的权值和，类似打表
tmp+=dfs(pos-1,sum+cost[i],limit&&(i==a[pos]));
if(!limit )
dp[pos][sum]=tmp; //记录可能会重复利用的数字
return tmp;
}
LL solve(LL x)//将整个16进制数各个位数拆分
{
int pos=0;
memset(a,0,sizeof(a)); //因为有多组数据，计算前先清空之前计算过的数据
while(x)
{
a[pos++]=x%16;
x/=16;
}
return dfs(7,0,1); //由于数组中各个位数排序位置与大数相反，所以最高位为下标为7的时候
}
int main()
{
int T;
scanf("%d",&T);
memset(dp,-1,sizeof(dp));
while(T--)
{
int setp;
char str[20];
scanf("%d %s",&setp,str);
setp--;
LL l=change(str); //将16进制字符转换为10进制数字
LL b=setp/mod; //每从0x00000000到0xffffffff是一个循环节，超过的用倍数统计即可
if(l+setp>=mod)
{
LL r=(l+setp)%mod;
printf("%lld\n",(b+1)*solve((LL)0xffffffff)-(solve(l-1)-solve(r)));
}
else
{
LL r=l+setp;
printf("%lld\n",solve(r)-solve(l-1));
}
}
return 0;
}