fork download
copy 
  1. //package CodeChef.LongChallenge.August2019;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.math.BigInteger;
  7.  
  8. class Encoding {
  9.  
  10.     static double POS = 100005;
  11.     static long[][][] DP = new long[(int)POS][10][2];
  12.     static long MOD = 1000000000 + 7;
  13.     static long[] tenpow = new long[(int)POS];
  14.  
  15.     private static long digitDP(int length, String number, int pos, int of, int prev) { //prev = block continues or no!
  16.         if (pos == length)
  17.             return 0;
  18.  
  19.         if (DP[pos][prev][of] != -1) {
  20.             return DP[pos][prev][of];
  21.         }
  22.  
  23.         if (prev > 0 && DP[pos][0][of] != -1) {
  24.             long tp = tenpow[length - (pos + 1)];
  25.             return DP[pos][prev][of] = ((DP[pos][0][of] % MOD) - ((((prev % MOD) * (tp % MOD)) % MOD) * (tp % MOD)) % MOD) % MOD;
  26.         }
  27.  
  28.         int maxDigit = 9;
  29.  
  30.         if (of == 0) {
  31.             maxDigit = number.charAt(pos) - 48;
  32.         }
  33.  
  34.         long res = 0L;
  35.  
  36.         for (int dgt = 0; dgt <= maxDigit; dgt++) {
  37.             int nof = of;
  38.             if (of == 0 && dgt < maxDigit) {
  39.                 nof = 1;
  40.             }
  41.  
  42.             res = ((res % MOD) + digitDP(length, number, pos + 1, nof, dgt) % MOD) % MOD;
  43.  
  44.             if (prev != dgt) {
  45.                 if (nof == 1) {
  46.                     long tp = tenpow[length - (pos + 1)];
  47.                     res = ((res % MOD) + ((((dgt % MOD) * (tp % MOD)) % MOD) * (tp % MOD)) % MOD) % MOD;
  48.                 } else {
  49.                     long tp = tenpow[length - (pos + 1)];
  50.                     res = ((res % MOD) + ((((dgt % MOD) * (tp % MOD)) % MOD) * (getN(pos, number) % MOD)) % MOD) % MOD;
  51.                 }
  52.             }
  53.  
  54. //            if (dgt == d) {
  55. //                if (prev == 0) {
  56. //                    //((res % MOD) + ((d * tenpow[length - (pos + 1)]) % MOD)) % MOD;
  57. //                    if (nof == 1) {
  58. //                        long tp = tenpow[length - (pos + 1)];
  59. //                        res = ((res % MOD) + ((((d % MOD) * (tp % MOD)) % MOD) * (tp % MOD)) % MOD) % MOD;
  60. //                    } else {
  61. //                        long tp = tenpow[length - (pos + 1)];
  62. //                        res = ((res % MOD) + ((((d % MOD) * (tp % MOD)) % MOD) * (getN(pos, number) % MOD)) % MOD) % MOD;
  63. //                    }
  64. //                }
  65. //            }
  66.         }
  67.  
  68.         return DP[pos][prev][of] = res;
  69.  
  70.     }
  71.  
  72.     private static long getN(int pos, String number) {
  73.         if (pos == number.length() - 1) {
  74.             return 1;
  75.         }
  76.         BigInteger bigInteger = new BigInteger(number.substring(pos + 1));
  77.         return bigInteger.mod(BigInteger.valueOf(MOD)).longValue() + 1;
  78.     }
  79.  
  80.     private static long solve(int length, String number) {
  81.         for (int i = 0; i < POS; i++) {
  82.             for (int j = 0; j < 10; j++) {
  83.                 DP[i][j][0] = -1; DP[i][j][1] = -1;
  84.             }
  85.         }
  86.         long ans = digitDP(length, number, 0, 0, 0) % MOD;
  87.         return ans;
  88.     }
  89.  
  90.     private static void calculateTenPow() {
  91.         long calc = 1;
  92.         tenpow[0] = 1;
  93.         for (int i = 1; i < (int)POS; i++) {
  94.             calc = ((calc % MOD) * 10) % MOD;
  95.             tenpow[i] = calc;
  96.         }
  97.     }
  98.  
  99.     public static void main(String[] args) throws IOException {
  100.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  101.         int T = Integer.parseInt(bufferedReader.readLine());
  102.         calculateTenPow();
  103.         while (T-- > 0) {
  104.             String[] input1 = bufferedReader.readLine().split(" ");
  105.             int lnum1 = Integer.parseInt(input1[0]);
  106.             String num1 = input1[1];
  107.             String[] input2 = bufferedReader.readLine().split(" ");
  108.             int lnum2 = Integer.parseInt(input2[0]);
  109.             String num2 = input2[1];
  110.             BigInteger bigInteger = new BigInteger(num1);
  111.             BigInteger bigInteger1 = bigInteger.subtract(BigInteger.ONE);
  112.             System.out.println((MOD + solve(lnum2, num2) - solve(lnum1, bigInteger1.toString())) % MOD);
  113.         }
  114.     }
  115. }
Runtime error #stdin #stdout #stderr 0.15s 74412KB
comments (?)
stdin
copy 
1
2 10
3 100
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 1
	at java.base/java.lang.StringLatin1.charAt(StringLatin1.java:47)
	at java.base/java.lang.String.charAt(String.java:702)
	at Encoding.digitDP(Main.java:31)
	at Encoding.digitDP(Main.java:42)
	at Encoding.solve(Main.java:86)
	at Encoding.main(Main.java:112)
https://ideone.com/sbQACa
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!