結果

問題 No.372 It's automatic
ユーザー 37zigen
提出日時 2016-05-14 13:39:25
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,346 bytes
コンパイル時間 2,183 ms
コンパイル使用メモリ 79,268 KB
実行使用メモリ 746,620 KB
最終ジャッジ日時 2024-10-06 02:27:38
合計ジャッジ時間 15,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

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[][] dp=new int[str.length()][m];
        /*
         * dp[i][j]=先頭からi+1文字までの部分文字列を考えたとき、
         * 余りjとなるものがいくつ存在するか。
         * ex.1021213421 (m=3)
         * dp[0][1]=1,dp[0][1]=0,dp[0][2]=0
         */
        if(str.charAt(0)-'0'==0){
            dp[str.length()-1][0]++;
        }else{
            dp[0][(str.charAt(0)-'0')%m]++;
        }
        for(int i=1;i<str.length();i++){
            /*
             * dp[i][]を考える
             */
            {
                for(int j=0;j<m;j++){
                    dp[i][(j*10+str.charAt(i)-'0')%m]+=dp[i-1][j];
                    dp[i][(j*10+str.charAt(i)-'0')%m]%=MOD;
                }
                if(str.charAt(i)-'0'!=0){
                    dp[i][(str.charAt(i)-'0')%m]++;
                }else if(str.charAt(i)-'0'==0){
                    dp[str.length()-1][0]++;
                }
                for(int j=0;j<m;j++){
                    dp[i][j]+=dp[i-1][j];
                    dp[i][j]%=MOD;
                }
            }
        }
        System.out.println(dp[str.length()-1][0]%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