結果

問題 No.372 It's automatic
ユーザー 37zigen
提出日時 2016-05-14 13:52:32
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,462 ms / 6,000 ms
コード長 1,340 bytes
コンパイル時間 2,247 ms
コンパイル使用メモリ 79,548 KB
実行使用メモリ 57,700 KB
最終ジャッジ日時 2024-10-06 02:30:19
合計ジャッジ時間 34,744 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package yukicoder;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        new Main().solve();
    }
    final int MOD=1_000_000_000+7;
    void solve(){
        Scanner sc=new Scanner(System.in);
        String str=sc.next();
        int m=sc.nextInt();
        
        int[] from=new int[m];
        int[] to=new int[m];
        
        /*
         * dp[i][j]=先頭からi+1文字までの部分文字列を考えたとき、
         * 余りjとなるものがいくつ存在するか。
         * ex.1021213421 (m=3)
         * dp[0][1]=1,dp[0][1]=0,dp[0][2]=0
         */
        
        int ZERO=0;
        if(str.charAt(0)-'0'==0){
            ZERO++;
        }else{
            from[(str.charAt(0)-'0')%m]++;
        }
        for(int i=1;i<str.length();i++){
            /*
             * dp[i][]を考える
             */
            {
                for(int j=0;j<m;j++){
                    to[(j*10+str.charAt(i)-'0')%m]+=from[j];
                    to[(j*10+str.charAt(i)-'0')%m]%=MOD;
                }
                if(str.charAt(i)-'0'!=0){
                    to[(str.charAt(i)-'0')%m]++;
                }else if(str.charAt(i)-'0'==0){
                    ZERO++;
                }
                for(int j=0;j<m;j++){
                    to[j]+=from[j];
                    to[j]%=MOD;
                }
            }
            from=to;to=new int[m];
        }
        System.out.println((from[0]+ZERO)%MOD);
    }
    void showMt(int[][] a){
        System.out.println("-------------");
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a[0].length;j++){
                System.out.print(a[i][j]+(j!=a[0].length-1?" ":"\n"));
            }
        }
        System.out.println("-------------");
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0