結果

問題 No.611 Day of the Mountain
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-12-11 02:05:46
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 5,569 bytes
コンパイル時間 2,022 ms
コンパイル使用メモリ 78,712 KB
実行使用メモリ 195,408 KB
最終ジャッジ日時 2024-05-07 17:04:12
合計ジャッジ時間 8,478 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.*;
import java.util.*;


class Main {
    static final long MOD=201712111;
    static final long I9=powerMod(9,MOD-2);
    static long[][][]dp2;
    static long powerMod(long x, long exponent) {
	long prod = 1;
	for (int i = 63; i >= 0; --i) {
	    prod = (prod * prod) % MOD;
	    if ((exponent & 1L << i) != 0) {
		prod = (prod * x) % MOD;
	    }
	}
	return prod;
    }
    Main(int h,int w,int[][]b){
        int[][]dp;
        dp=new int[h][w];
        for(int i=0;i<w;++i)
            dp[0][i]=b[0][i]==-1?1:b[0][i];
        for(int i=1;i<h;++i)
            for(int j=0;j<w;++j){
                int c=b[i][j]==-1?1:b[i][j];
                int m=Integer.MAX_VALUE;
                m=Math.min(m,dp[i-1][j]+c);
                if(j>0)m=Math.min(m,dp[i-1][j-1]+c);
                dp[i][j]=m;
            }
        int indet=0;
        for(int[]r:b)
            for(int rr:r)
                if(rr==-1)indet++;
        long[][]dp2=new long[h][1<<w];
            dp2[0][1]=b[0][0]==-1?I9:1;
        for(int i=1;i<h;++i)
            for(int s=0;s<1<<w;++s){
                int p=0;
                int ps=0;
                int[][]alt=new int[w][2];
                long factor=1;
                for(int j=0;j<w;++j){
                    if((s&1<<j)==0)continue;
                    int c=b[i][j]==-1?1:b[i][j];
                    if(b[i][j]==-1)factor=factor*I9%MOD;
                    int m=Integer.MAX_VALUE;
                    alt[ps][0]=alt[ps][1]=0;
                    if(dp[i-1][j]+c==dp[i][j])
                        alt[ps][0]=1<<j;
                    if(j>0&&dp[i-1][j-1]+c==dp[i][j])
                        alt[ps][1]=1<<(j-1);
                    if(alt[ps][0]==0)
                        alt[ps][0]=alt[ps][1];
                    if(alt[ps][1]==0)
                        alt[ps][1]=alt[ps][0];
                    if(alt[ps][0]==alt[ps][1])
                        p|=alt[ps][0];
                    else
                        ps++;
                }
                long total=0;
                int[]taplis=new int[1<<ps];
                for(int a=0;a<1<<ps;++a){
                    int q=0;
                    for(int l=0;l<ps;++l)
                        if((a&1<<l)!=0)
                            q|=alt[l][1];
                        else
                            q|=alt[l][0];
                    taplis[a]=q;
                }
                for(int a=1;a<1<<(1<<ps);++a){
                    int q=0;
                    for(int l=0;l<1<<ps;++l){
                        if((a&1<<l)!=0)
                            q|=taplis[l];
                    }
                    long sgn=1;
                    int disp=1;
                    if(Integer.bitCount(a)%2==0){
                        sgn=MOD-1;
                        disp=-1;
                    }
                    total=(total+sgn*dp2[i-1][p|q])%MOD;
                }
                dp2[i][s]=total*factor%MOD;//TODO
            }
        
        // System.err.println(Arrays.deepToString(dp));
        // System.err.println("indet="+indet);
        out.println(dp[h-1][w-1]);
        long ans=powerMod(9,indet);
        for(int i=0;i<h;++i)
            for(int j=0;j<1<<w;++j)
                dp2[i][j]=dp2[i][j]*ans%MOD;
        // System.err.println(Arrays.deepToString(dp2));
        out.println(dp2[h-1][1<<(w-1)]);
    }
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int h=sc.nextInt();
        int w=sc.nextInt();
        String[]s=new String[h];
        for(int i=0;i<h;++i)s[i]=sc.next();
        int[][]b,dp;
        b=new int[h][w];
        for(int i=0;i<h;++i)
            for(int j=0;j<w;++j){
                char c=s[i].charAt(j);
                b[i][j]=c=='?'?-1:c-'0';
            }
        if(h<w){
            int[][]c=new int[w][h];
            for(int i=0;i<h;++i)
                for(int j=0;j<w;++j)
                    c[j][i]=b[i][j];
            b=c;
            int t=h;
            h=w;
            w=t;
        }
        int[][]c=new int[h+w-1][w];
        for(int i=0;i<h+w-1;++i)Arrays.fill(c[i],1000);
        for(int i=0;i<h;++i)
            for(int j=0;j<w;++j)
                c[i+j][j]=b[i][j];
        new Main(h+w-1,w,c);
        
        out.close();
    }
    // http://codeforces.com/blog/entry/7018
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
0