#63891 (Java) No.315 世界のなんとか3.5

• 問題: No.315 世界のなんとか3.5
• ユーザー: ぴろず
• 提出日時: 2015-12-08 13:46:11
• 言語: Java (openjdk 23)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 2,369 bytes
• コンパイル時間: 2,468 ms
• コンパイル使用メモリ: 77,896 KB
• 実行使用メモリ: 71,140 KB
• 最終ジャッジ日時: 2024-09-14 19:55:39
• 合計ジャッジ時間: 34,156 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 30 TLE * 6

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package no315;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static long MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        int zeros = sc.next().length() - 1;
        long bb = aho(b,zeros);
        long aa = aho(new BigInteger(a).subtract(BigInteger.ONE).toString(),zeros);
        System.out.println((bb + MOD - aa) % MOD);
    }
    public static boolean useNaive = false;
    public static long aho(String ss,int zeros) {
        if (useNaive && ss.length() <= 5) {
            return naiveAho(Integer.parseInt(ss), zeros);
        }
        char[] s = ss.toCharArray();
        int n = Math.max(0,s.length - 3 - zeros);
        int[][][] dp = new int[2][4][n+1];
        dp[1][0][0] = 1;
        for(int i=0;i<n;i++) {
            for(int large=0;large<2;large++) {
                for(int j=0;j<4;j++) {
                    int max = large == 0 ? 9 : s[i] - '0';
                    for(int k=0;k<=max;k++) {
                        int nlarge = large & (k == max ? 1 : 0);
                        int nj = (j == 3 || k == 3) ? 3 : (j + k) % 3;
                        dp[nlarge][nj][i+1] += dp[large][j][i];
                        if (dp[nlarge][nj][i+1] >= MOD) {
                            dp[nlarge][nj][i+1] -= MOD;
                        }
                    }
                }
            }
        }
        long ans = 0;
        int max = 1000;
        int step = 8;
        for(int i=0;i<zeros;i++) {
            max *= 10;
            step *= 10;
        }
        int tail = Integer.parseInt(ss.substring(n, ss.length()));
        for(int i=0;i<max;i++) {
            if (i % step == 0) {
                continue;
            }
            int sum = 0;
            boolean three = false;
            int x = i;
            while(x > 0) {
                int d = x % 10;
                sum += d;
                if (d == 3) {
                    three = true;
                    break;
                }
                x /= 10;
            }
            for(int large=0;large<2;large++) {
                if (large == 1 && i > tail) {
                    continue;
                }
                for(int j=0;j<4;j++) {
                    if (j == 3 || three || (j+sum)%3==0) {
                        if (dp[large][j][n] > 0) {
//                          System.out.println(i + "," + large + "," + j + "," + n);
                        }
                        ans += dp[large][j][n];
                    }
                }
            }
        }
        return ans % MOD;
    }
    public static long naiveAho(int max,int zeros) {
        long ans = 0;
        int step = 8;
        for(int i=0;i<zeros;i++) {
            step *= 10;
        }
        for(int i=0;i<=max;i++) {
            if (i % step == 0) {
                continue;
            }
            int x = i;
            boolean three = false;
            while(x > 0) {
                int d = x % 10;
                if (d == 3) {
                    three = true;
                    break;
                }
                x /= 10;
            }
            if (i % 3 == 0 || three) {
                ans++;
            }
        }
        return ans;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX