結果
| 問題 |
No.611 Day of the Mountain
|
| コンテスト | |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2017-12-11 02:05:46 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,569 bytes |
| コンパイル時間 | 2,054 ms |
| コンパイル使用メモリ | 78,788 KB |
| 実行使用メモリ | 196,976 KB |
| 最終ジャッジ日時 | 2024-11-30 11:32:10 |
| 合計ジャッジ時間 | 20,553 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 4 TLE * 5 |
ソースコード
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;
}
}
}