首页 > 试题广场 >

小红删数字

[编程题]小红删数字
  • 热度指数：2522 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 的整数数组 a_1,a_2,\dots,a_n。需要进行恰好 n-1 次操作，数组最终只剩下一个数字。

\hspace{15pt}每次操作只能针对当前数组的最后两个数 x,y（x 在前，y 在后）执行下述二选一：
\hspace{23pt}\bullet\, 将 x,y 删除，并将 \bigl(x+y\bigr) \bmod 10 插入到数组末尾；
\hspace{23pt}\bullet\, 将 x,y 删除，并将 \bigl(x\times y\bigr) \bmod 10 插入到数组末尾。

\hspace{15pt}请统计，在所有可能的操作序列下，最终结果为 0,1,\dots,9 的方案数各有多少。答案对 10^9+7 取模。

输入描述:
\hspace{15pt}第一行输入整数 n\ (1\leqq n\leqq200\,000)——数组长度。

\hspace{15pt}第二行输入 n 个整数 a_1,\dots,a_n\ (1\leqq a_i\leqq10^9)——初始数组。


输出描述:
\hspace{15pt}输出一行 10 个整数，第 i 个数表示最终结果为 i 的方案数（按 \bmod\ 10^9+7）。
示例1

输入

4
1 2 3 4

输出

1 0 0 0 3 3 0 0 0 1
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 60浏览

热门推荐

相关试题

小红删数字

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号