#P17906. LED Display Renovation

    ID: 17192 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300提高全子集枚举分组背包线性 DP计数 DP滚动数组

LED Display Renovation

题目描述

有一个包含 nn 个数字块的七段 LED 显示器。每个段的初始状态为 W(正常)、1(始终点亮)或 0(始终熄灭)。正常段可以按需要点亮或熄灭,故障段则保持固定状态。

选择至多 kk 个段进行翻新,使其变为正常状态。初始正常的段也允许翻新;每段至多选择一次。两种方案不同,当且仅当选择的段集合不同。

翻新后,一个非负整数能够被正确显示,需要满足:

  • 十进制位数不超过 nn,右对齐显示。
  • 除整数 00 本身外,不能出现前导零。
  • 没有使用的左侧数字块必须完全熄灭。
  • 使用的每个数字块必须符合对应数字的全部七段状态。

求可以正确显示的整数数量的最大值,以及达到该最大值的翻新方案数。方案数输出精确整数,不取模。

输入格式

第一行是测试组数 TT。每组先输入 n,kn,k,随后输入七行 ASCII 图像,每行长度恰好为 5n−15n-1。每个数字块占四列,相邻块之间隔一列 .。段由两个相同字符表示,其余位置必须为 .。

单个数字块的布局如下,数字表示段编号,并非实际输入字符:

.00.
1..2
1..2
.33.
4..5
4..5
.66.

按段编号 0,1,…,60,1,\ldots,6 排列,十个数字需要的点亮状态为:

数字 七段状态
0 1110111
1 0010010
2 1011101
3 1011011
4 0111010
5 1101011
6 1101111
7 1010010
8 1111111
9 1111011

输出格式

每组输出两个整数:最大可显示整数数目、最优翻新方案数。

数据范围

1≤T≤1001\le T\le100,1≤n≤91\le n\le9,1≤k<7n1\le k<7n。没有额外的多测总规模限制。

样例输入

1
1 1
.WW.
W..W
W..W
.WW.
W..W
W..W
.WW.

样例输出

10 8

样例说明

这是用于说明格式的自拟样例。所有数字都可以显示;不翻新或翻新七个段中的任意一个,共八种方案。