| 信息学奥赛一本通 1313：【例3.5】位数问题 | 您所在的位置：网站首页 › 信息学奥赛一本通1011答案 › 信息学奥赛一本通 1313：【例3.5】位数问题 |
|
【题目链接】
ybt 1313：【例3.5】位数问题 【题目考点】 1. 递推 【解题思路】设 M = 12345 M=12345 M=12345 a[i]表示i位数的数字中，有偶数个3的数字的数量对M取模。 b[i]表示i位数的数字中，有奇数个3的数字的数量对M取模。 1位数只有数字 3 3 3包含1个3，也就是奇数个3。其余9个数字都只包含0个3，也就是偶数个3。 那么a[1]=9 表示在1位数中有9个数字有偶数个3, b[1] = 1 表示在1位数中有1个数字有奇数个3。2位数，就是在1位数前面添加一位数字。假设n>2，即第2位不是最高位。 那么2位数字有偶数个3的情况有： 第一位为3第二位为3： 1 ∗ 1 = 1 1 * 1=1 1∗1=1 第一位不为3第二位不为3： 9 ∗ 9 = 81 9 * 9 = 81 9∗9=81 一共有82种情况，所以 a [ 2 ] = 82 a[2] = 82 a[2]=82，表示在2位数中，有82个数字有偶数个3。 同理： b [ 2 ] = 1 ∗ 9 + 9 ∗ 1 = 18 b[2] = 1 * 9 + 9 * 1 = 18 b[2]=1∗9+9∗1=18 ，表示在2位数中，有18个数字有奇数个3考虑一般情况，假设i if(i == n)//最后一次添加数字，添加的是最高位数字，不能添加0，所以不添加3的情况只有8种 x--; a[i] = (a[i-1]*x + b[i-1])%M; b[i] = (a[i-1] + b[i-1]*x)%M; } cout |
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 |