号码显示屏用 7 根灯管表示一个数字。
每个数字亮起的灯管数如下：0 亮 6 根，1 亮 2 根，2 亮 5 根，3 亮 5 根，4 亮 4 根，5 亮 5 根，6 亮 6 根，7 亮 3 根，8 亮 7 根，9 亮 6 根。
在显示屏上显示整数 x 时，亮起的是 x 用十进制、不加前导 0 写出的各个数字。
0 用一个数字 0 显示。
x 的灯管数是亮起的各个数字的灯管数之和。
例如 108 的灯管数是 2 + 6 + 7 = 15，7 的灯管数是 3。
对每个问题，输出 L 以上 R 以下的整数中灯管数恰好为 S 的有多少个。
没有这样的整数时输出 0。
3 1 20 5 0 9 6 100 200 15
4 3 6
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
R 可达 10^15，不能逐个去数。
用数位 DP：ways[k][s] = 任意排列 k 个数字时灯管数之和为 s 的方法数（k = 16、s ≤ 112 就够了）。
写出“0 到 n 中灯管数为 S 的数的个数”count(n)，答案是 count(R) − count(L − 1)。count(n) 分三部分：① 0 本身（6 根灯管）② 位数比 n 少的数 — 首位是 1～9，其余 k − 1 位用 ways ③ 位数与 n 相同的数 — 从前往后沿着 n 的数字走，在第 i 位第一次选了更小的数字 d，后面就是 ways[剩余位数][剩余灯管]（首位从 1 开始）。
走到最后的 n 本身也要算一个。
例：1～20 中 5 根灯管的是 2、3、5、17（2 + 3），共 4 个。
陷阱一：像数位和计数的常见写法那样给短的数补前导 0 按同样长度去数是错的 — 数位和里 0 贡献 0 所以没问题，这里每个前导 0 却算亮了 6 根灯管。
要按位数分开数，或者把“是否已经开始写数字”放进状态。
陷阱二：漏掉 0 本身，L = 0、S = 6 的问题会少一个。
陷阱三：用 count(R) − count(L) 相减会漏掉 L 本身。
陷阱四：有些显示屏把 7 画成 4 根、6 和 9 画成 5 根 — 要按本题的表（7 是 3 根，6、9 是 6 根）来。
陷阱五：答案接近 10^15，超过 32 位 int（约 21 亿）。
C、C++ 要用 long long，Java、C# 要用 long（Java 中用 += 把 long 加到 int 上也能编译，并悄悄截断 — 因为复合赋值会自动转换类型；C# 会编译报错），输入也要用 Long.parseLong、long.Parse、%lld 读。
Python 的整数没有上限，JavaScript、TypeScript、Craykon 的数是双精度浮点数，在 2^53（约 9×10^15）以内是精确的，直接用就行。
把数变成数字串：Python str(n)，JS/TS String(n)，Java Long.toString(n)，C# n.ToString()，C snprintf(buf, size, "%lld", n)，C++ std::to_string(n)，Craykon "" + n（10^15 也不会写成指数形式）和 digits[i].转数字()。
import sys SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] # 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16 # 10^15는 16자리MAXS = 7 * MAXLEN # ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [[0] * (MAXS + 1) for _ in range(MAXLEN + 1)]ways[0][0] = 1for k in range(1, MAXLEN + 1): for s in range(MAXS + 1): if ways[k - 1][s]: for d in range(10): ways[k][s + SEG[d]] += ways[k - 1][s] def tail(k, s): """뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수""" return ways[k][s] if 0 <= s <= MAXS else 0 def count_upto(n, S): """0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수""" if n < 0: return 0 total = 1 if S == SEG[0] else 0 # 0은 숫자 0 하나로 띄운다 if n == 0: return total digits = str(n) length = len(digits) # n보다 자릿수가 적은 수: 첫 숫자는 1~9(앞에 0을 붙이지 않는다), 나머지는 아무 숫자 for k in range(1, length): for d in range(1, 10): total += tail(k - 1, S - SEG[d]) # n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S for i, ch in enumerate(digits): c = int(ch) for d in range(1 if i == 0 else 0, c): total += tail(length - 1 - i, rest - SEG[d]) rest -= SEG[c] if rest == 0: total += 1 # n 자신 return total data = sys.stdin.read().split()q = int(data[0])out = []for i in range(q): lo, hi, s = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i]) out.append(str(count_upto(hi, s) - count_upto(lo - 1, s)))print("\n".join(out))const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/); const SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways = Array.from({ length: MAXLEN + 1 }, () => new Array(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }} const tail = (k, s) => (s >= 0 && s <= MAXS ? ways[k][s] : 0); // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n, S) { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;} const q = Number(data[0]);const out = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));import { readFileSync } from "node:fs"; const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/); const SEG: readonly number[] = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수const MAXLEN = 16; // 10^15는 16자리const MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수// 가장 큰 값도 10^15쯤이라 number(2^53까지 정확)로 충분하다const ways: number[][] = Array.from({ length: MAXLEN + 1 }, () => new Array<number>(MAXS + 1).fill(0));ways[0][0] = 1;for (let k = 1; k <= MAXLEN; k++) { for (let s = 0; s <= MAXS; s++) { if (ways[k - 1][s] === 0) continue; for (let d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; }} function tail(k: number, s: number): number { return s >= 0 && s <= MAXS ? ways[k][s] : 0;} // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수function countUpto(n: number, S: number): number { if (n < 0) return 0; let total = S === SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n === 0) return total; const digits = String(n); const len = digits.length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (let k = 1; k < len; k++) { for (let d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 let rest = S; for (let i = 0; i < len; i++) { const c = digits.charCodeAt(i) - 48; for (let d = i === 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest === 0) total += 1; // n 자신 return total;} const q = Number(data[0]);const out: number[] = [];for (let i = 0; i < q; i++) { const lo = Number(data[1 + 3 * i]); const hi = Number(data[2 + 3 * i]); const s = Number(data[3 + 3 * i]); out.push(countUpto(hi, s) - countUpto(lo - 1, s));}console.log(out.join("\n"));import java.io.*;import java.util.*; public class Main { static final int[] SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수 static final int MAXLEN = 16; // 10^15는 16자리 static final int MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static final long[][] ways = new long[MAXLEN + 1][MAXS + 1]; static long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; } // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long countUpto(long n, int S) { if (n < 0) return 0; long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; String digits = Long.toString(n); int len = digits.length(); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits.charAt(i) - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total; } public static void main(String[] args) throws IOException { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s] != 0) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long lo = Long.parseLong(st.nextToken()); long hi = Long.parseLong(st.nextToken()); int s = Integer.parseInt(st.nextToken()); sb.append(countUpto(hi, s) - countUpto(lo - 1, s)).append('\n'); } System.out.print(sb); }}using System;using System.Text; class Program{ static readonly int[] Seg = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; // 숫자 0~9를 띄울 때 켜지는 막대 수 const int MaxLen = 16; // 10^15는 16자리 const int MaxS = 7 * MaxLen; // ways[k, s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 static readonly long[,] Ways = new long[MaxLen + 1, MaxS + 1]; static long Tail(int k, int s) => s >= 0 && s <= MaxS ? Ways[k, s] : 0; // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long) static long CountUpto(long n, int S) { if (n < 0) return 0; long total = S == Seg[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; string digits = n.ToString(); int len = digits.Length; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += Tail(k - 1, S - Seg[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += Tail(len - 1 - i, rest - Seg[d]); rest -= Seg[c]; } if (rest == 0) total++; // n 자신 return total; } static void Main() { Ways[0, 0] = 1; for (int k = 1; k <= MaxLen; k++) for (int s = 0; s <= MaxS; s++) if (Ways[k - 1, s] != 0) for (int d = 0; d < 10; d++) Ways[k, s + Seg[d]] += Ways[k - 1, s]; int q = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { var p = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); long lo = long.Parse(p[0]); long hi = long.Parse(p[1]); int s = int.Parse(p[2]); sb.Append(CountUpto(hi, s) - CountUpto(lo - 1, s)).Append('\n'); } Console.Write(sb); }}#include <array>#include <iostream>#include <string> constexpr int MAXLEN = 16; // 10^15는 16자리constexpr int MAXS = 7 * MAXLEN;constexpr std::array<int, 10> SEG = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 숫자 0~9를 띄울 때 켜지는 막대 수 // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수std::array<std::array<long long, MAXS + 1>, MAXLEN + 1> ways{}; long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; } // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long)long long countUpto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; // 0은 숫자 0 하나로 띄운다 if (n == 0) return total; const std::string digits = std::to_string(n); const int len = static_cast<int>(digits.size()); // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; // n 자신 return total;} int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; std::cin >> q; for (int i = 0; i < q; i++) { long long lo, hi; int s; std::cin >> lo >> hi >> s; std::cout << countUpto(hi, s) - countUpto(lo - 1, s) << '\n'; }}#include <stdio.h> #define MAXLEN 16 /* 10^15는 16자리 */#define MAXS (7 * MAXLEN) static const int SEG[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /* 숫자 0~9를 띄울 때 켜지는 막대 수 *//* ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수 */static long long ways[MAXLEN + 1][MAXS + 1]; static long long tail(int k, int s) { return s >= 0 && s <= MAXS ? ways[k][s] : 0; } /* 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수(답이 10^15까지 가서 long long) */static long long count_upto(long long n, int S) { if (n < 0) return 0; long long total = S == SEG[0] ? 1 : 0; /* 0은 숫자 0 하나로 띄운다 */ if (n == 0) return total; char digits[24]; int len = snprintf(digits, sizeof digits, "%lld", n); /* n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 */ for (int k = 1; k < len; k++) for (int d = 1; d <= 9; d++) total += tail(k - 1, S - SEG[d]); /* n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 */ int rest = S; for (int i = 0; i < len; i++) { int c = digits[i] - '0'; for (int d = i == 0 ? 1 : 0; d < c; d++) total += tail(len - 1 - i, rest - SEG[d]); rest -= SEG[c]; } if (rest == 0) total++; /* n 자신 */ return total;} int main(void) { ways[0][0] = 1; for (int k = 1; k <= MAXLEN; k++) for (int s = 0; s <= MAXS; s++) if (ways[k - 1][s]) for (int d = 0; d < 10; d++) ways[k][s + SEG[d]] += ways[k - 1][s]; int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { long long lo, hi; int s; scanf("%lld %lld %d", &lo, &hi, &s); printf("%lld\n", count_upto(hi, s) - count_upto(lo - 1, s)); } return 0;}SEG = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]; // 숫자 0~9를 띄울 때 켜지는 막대 수MAXLEN = 16; // 10^15는 16자리MAXS = 7 * MAXLEN; // ways[k][s] = 숫자 k개를 아무렇게나 늘어놓았을 때(0으로 시작해도 된다) 막대 수 합이 s인 경우의 수ways = [];循环 (k = 0; k <= MAXLEN; k++){ ways.添加(新列表(MAXS + 1, 0));}ways[0][0] = 1;循环 (k = 1; k <= MAXLEN; k++){ 循环 (s = 0; s <= MAXS; s++) { 如果 (ways[k - 1][s] != 0) { 循环 (d = 0; d < 10; d++) { ways[k][s + SEG[d]] += ways[k - 1][s]; } } }} // 뒤에 숫자 k개가 남았고 막대를 s개 더 켜야 할 때의 경우의 수뒤(k, s){ 如果 (s < 0 || s > MAXS) { 返回 0; } 返回 ways[k][s];} // 0 이상 n 이하의 정수 가운데 막대 수가 S인 것의 수세기(n, S){ 如果 (n < 0) { 返回 0; } total = 0; 如果 (S == SEG[0]) { total = 1; } 如果 (n == 0) { 返回 total; } digits = "" + n; len = digits.长度; // n보다 자릿수가 적은 수: 첫 숫자는 1~9, 나머지는 아무 숫자 循环 (k = 1; k < len; k++) { 循环 (d = 1; d <= 9; d++) { total += 뒤(k - 1, S - SEG[d]); } } // n과 자릿수가 같은 수: 앞에서부터 n과 같다가 처음 더 작아지는 자리를 고른다 rest = S; 循环 (i = 0; i < len; i++) { c = digits[i].转数字(); 시작 = 0; 如果 (i == 0) { 시작 = 1; } 循环 (d = 시작; d < c; d++) { total += 뒤(len - 1 - i, rest - SEG[d]); } rest -= SEG[c]; } 如果 (rest == 0) { total += 1; } 返回 total;} q = 控制台.读行().去空白().转数字();循环 (i = 0; i < q; i++){ p = 控制台.读数字(); 控制台.输出(세기(p[1], p[2]) - 세기(p[0] - 1, p[2]));}