海南哪家公司做网站,开发一套管理系统多少钱,电子产品配件采购网站,微信营销策划方案范文目录 [SCOI2013]数数
题目描述
输入描述:
输出描述:
输入
输出
说明
思路#xff1a;
代码实现#xff1a; [SCOI2013]数数 G-[SCOI2013]数数_牛客竞赛动态规划专题班数位dp练习 (nowcoder.com)
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制
代码实现 [SCOI2013]数数 G-[SCOI2013]数数_牛客竞赛动态规划专题班数位dp练习 (nowcoder.com)
时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld
题目描述
Fish 是一条生活在海里的鱼有一天他很无聊就开始数数玩。 他数数玩的具体规则是
1. 确定数数的进制B
2. 确定一个数数的区间[L, R]
3. 对于[L, R] 间的每一个数把该数视为一个字符串列出该字符串的每一个连续的子串对应的B进制数的值。
4. 对所有列出的数求和。
现在Fish 数了一遍数但是不确定自己的结果是否正确了。由于[L, R] 较大他没有多余精力去验证是否正确你能写一个程序来帮他验证吗
输入描述:
输入包含三行。
第一行仅有一个数B表示数数的进制。
第二行有N 1 个数第一个数为N表示数L在B 进制下的长度为N接下里的N个数从高位到低位的表示数L 的具体每一位。
第三行有M 1 个数第一个数为M表示数R 在B 进制下的长度为M接下里的M个数从高位到低位的表示数R 的具体每一位。
20% 数据0 ≤ R ≤ L ≤ 10^5。
50% 数据2 ≤ B ≤ 10001 ≤ N,M ≤ 1000。
100% 数据2 ≤ B ≤ 10^51 ≤ N,M ≤ 10^5。
输出描述:
输出仅一行即按照Fish 数数规则的结果结果用10 进制表示由于该数可能很大输出该数模上20130427的模数。
示例1
输入
复制10 3 1 0 3 3 1 0 3
10
3 1 0 3
3 1 0 3
输出
复制120
120
说明
Hint
[103, 103] 之间仅有数103该数的所有子串包括1, 10, 103, 0, 03, 3其和为120。
思路
还是用数位dp的思路计算0-r的值v1和0-l的值v2然后利用v1-v2因为他是输入的字符串你计算l-1还要考虑它的位之类的很烦那我们直接单独计算l的贡献值v3则答案就为v1-v2v3。
现在给出计算思路
这一位填0填0就只需要考虑当前填的0是否是先导0如果是先导0则只需要统计下一位的贡献即可如果不是先导0则需要统计下一位的额外贡献。 例如 1050 他的字串为 1 10 105 1050、 0 05 050、 5 50、 0它下一位的贡献为55 5*110但是因为他不是先导0对0这位还有额外贡献55也应该计算。 例如 0050 他的子串为 5 50、 0它就只有下一位的贡献为55对上一位的0没有贡献。这一位填1-x-1填1-x-1的话对下一位来说他就一定没有这位填数的大小的限制即下一位可以填0-B-1然后他的贡献是 x * x-1/2还要考虑下一位的额外贡献还要考虑这样的贡献包括额外贡献的次数能有多少次。 例如 12789前两位填 11则这一位的贡献为 10*9/2 * 110100后面的位共有100种可以搭配的选择所以这一位的贡献为10*9/2 * 110100*100。110100表示它在子串中可能出现的各种位置的贡献。这一位填x对下一位来说它有没有限制需要看这一位有没有限制如果没有限制即下一位可以填0-B-1否则它只能选择的情况为题目的数据大小然后他的贡献是 x还要考虑下一位的额外贡献还要考虑这样的贡献能有多少次。这样的统计才是完整的。
代码实现 public class Ex {static int N 100010;static long[][][] dp new long[N][2][2];static int len;static int B;static int[] l new int[N];static int[] r new int[N];static int[] arr new int[N];static long[] pw new long[N];static long[] s new long[N];static long[] suf new long[N];static int mod 20130427;public static void main(String[] args) {Scanner input new Scanner(System.in);B input.nextInt();pw[1] 1; s[1] 1;for(int i 2; i N; i ) {pw[i] pw[i - 1] * B % mod;s[i] (s[i - 1] pw[i] ) % mod;}int n input.nextInt();for(int i 1; i n; i) {l[i] input.nextInt();}int m input.nextInt();for(int i 1; i m; i) {r[i] input.nextInt();}
// System.out.println(solve(r, m));
// System.out.println(solve(l, n));
// System.out.println(get(l, n));System.out.println((solve(r, m) - solve(l, n) modget(l,n)) % mod);}public static long get(int[] a, int n){long res 0;for (int i 1; i n; i) {res (res (long) i * a[i] % mod * s[n - i 1] % mod) % mod;}return res;}public static long solve(int[] a, int n){len n;arr a;for (int i 0; i N; i) {for (int j 0; j 2; j) {Arrays.fill(dp[i][j], -1);}}suf[n 1] 0;for (int i n; i 1; i--) {// 这里计算如果在有限制的情况下数据可能有多少种。即这样的贡献的贡献次数suf[i] (suf[i 1] pw[n - i 1] * arr[i] % mod) % mod; }return dfs(1, 1, false)[0];}public static long[] dfs(int pos, int pre, boolean flag) {if (pos len) return new long[]{0,0};int x flag ? B-1:arr[pos];if (flag dp[pos][pre][0] ! -1) return dp[pos][pre];long[] ans new long[2];long[] tmp dfs(pos 1, pre, flag || x ! 0); // 填0// tmp[0] 下一位的贡献 pre 1 ? 0 : 1) * tmp[1] 如果不是先导0这里应该有额外贡献ans[0] (ans[0] ((pre 1 ? 0 : 1) * tmp[1]) tmp[0]) % mod;ans[1] (ans[1] tmp[1]) % mod;if (x 1) { //填 1 到 x - 1long xx x - 1;long cnt pw[len - pos 1]; // 贡献次数tmp dfs(pos 1, 0, true);// s[len - pos 1] * ( xx * x) / 2 % mod * cnt % mod 这一位提供的贡献// tmp[0] * xx % mod 下一位提供的贡献// tmp[1] * xx % mod 下一位提供的额外贡献ans[0] (ans[0] s[len - pos 1] * ( xx * x) / 2 % mod * cnt % mod tmp[0] * xx % mod tmp[1] * xx % mod) % mod;// 计算这一位能提供的额外贡献ans[1] (ans[1] s[len - pos 1] * ( xx * x) / 2 % mod * cnt % mod tmp[1] * xx % mod) % mod;}if (x 0) { // 填xlong cnt flag ? pw[len - pos 1] : suf[pos 1] 1; // 贡献次数tmp dfs(pos 1, 0, flag);// 和上一个类似ans[0] ((long) s[len - pos 1] * x % mod * cnt % mod ans[0] tmp[0] tmp[1]) % mod;ans[1] ((long) s[len - pos 1] * x % mod * cnt % mod ans[1] tmp[1]) % mod;}if (flag) dp[pos][pre] ans;return ans;}}
