简答题 偏难
#7161

数字构造 火山宝打算造一个 n 位的十进制数字出来。 对于 1 到 n 中的每一个 i,火山宝可以从 x i ,1, ..., x i ,k i 这 k i 个…

数字构造

火山宝打算造一个 n 位的十进制数字出来。

对于 1 到 n 中的每一个 i,火山宝可以从 xi,1, ..., xi,ki 这 ki 个 0-9 的数字中选择一个作为 ai。

在选择结束后,a1a2...an 形成了一个 n 位的十进制数——这就是火山宝造出来的数。

你需要帮火山宝计算他能造出的数中,有多少个是 3 的倍数。

时间限制:1000

内存限制:65536

输入

第一行输入一个整数 n(1 ≤ n ≤ 18),表示数字的位数。 接下来 n 行,每行第一个整数 ki (1 ≤ ki ≤ 10),表示第 i 中候选的数字数量。接着是 ki 个两两不同的 0-9 范围内的数字 xi,1, ..., xi,ki。 输入保证 0 不是第一位的可选项。

输出

你需要输出一行一个整数,表示火山宝能造出的数字中,3 的倍数的数量。

样例输入

样例输入1:

2
5 5 6 7 8 9
5 0 1 2 3 4

样例输入2:

5
9 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9

样例输出

样例输出1:

9

样例输出2:

30000

提示

样例1能造出来的 3 的倍数有 51, 54,60,63,72,81,84,90, 93。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int num[20][10]; int k[20]; int mod[20][3] = {}; int main() {   int n;   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; k[i];     for (int j = 0; j &lt; k[i]; j++) {       cin &gt;&gt; num[i][j];       mod[i][num[i][j] % 3]++;     }   }   long result[3] = {};   for (int i = 0; i &lt; 3; i++)     result[i] = mod[0][i];   for (int i = 1; i &lt; n; i++) {     long temp0 = result[0], temp1 = result[1], temp2 = result[2];     result[0] = temp0 * mod[i][0] + temp1 * mod[i][2] + temp2 * mod[i][1];     result[1] = temp0 * mod[i][1] + temp1 * mod[i][0] + temp2 * mod[i][2];     result[2] = temp0 * mod[i][2] + temp1 * mod[i][1] + temp2 * mod[i][0];   }   cout &lt;&lt; result[0] &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。