結果
| 問題 |
No.611 Day of the Mountain
|
| コンテスト | |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2017-12-11 21:44:57 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 511 ms / 2,017 ms |
| コード長 | 7,794 bytes |
| コンパイル時間 | 2,311 ms |
| コンパイル使用メモリ | 89,748 KB |
| 実行使用メモリ | 43,028 KB |
| 最終ジャッジ日時 | 2024-11-30 21:01:47 |
| 合計ジャッジ時間 | 5,664 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 |
ソースコード
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;
}
void oldMain(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;
}
if(true){
System.err.println("i="+i);
System.err.println("s="+s);
System.err.println("taplis="+Arrays.toString(taplis));
}
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)]);
}
Main(int h,int w,int[][]b){
int[][]dp;
dp=new int[h][w];
dp[0][0]=b[0][0]==-1?1:b[0][0];
for(int i=0;i<h;++i)
for(int j=0;j<w;++j){
if(i+j==0)continue;
int c=b[i][j]==-1?1:b[i][j];
int m=Integer.MAX_VALUE;
if(i>0)m=Math.min(m,dp[i-1][j]+c);
if(j>0)m=Math.min(m,dp[i][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[2][1<<w];
dp2[0][0]=1;
dp2[0][1]=b[0][0]==-1?I9:1;
for(int i=0;i<h;++i){
for(int j=0;j<w;++j){
if(i+j==0)continue;
int c=b[i][j]==-1?1:b[i][j];
long factor=b[i][j]==-1?I9:1;
int u=(i*w+j)%2;
int pr=1-u;
for(int s=0;s<1<<w;++s){
if(s%2==0){
dp2[u][s]=dp2[pr][s/2];
continue;
}
boolean up=i>0&&dp[i][j]==dp[i-1][j]+c;
boolean lft=j>0&&dp[i][j]==dp[i][j-1]+c;
int lftS=s>>1|1;
int upS=s>>1|1<<(w-1);
long ans;
if(lft&&up)
ans=(dp2[pr][lftS]+dp2[pr][upS]-dp2[pr][lftS|upS]+MOD)%MOD;
else if(lft)
ans=dp2[pr][lftS];
else if(up)
ans=dp2[pr][upS];
else
throw new Error();
dp2[u][s]=ans*factor%MOD;
}
}
}
out.println(dp[h-1][w-1]);
long ans=powerMod(9,indet);
for(int i=0;i<2;++i)
for(int j=0;j<1<<w;++j)
dp2[i][j]=dp2[i][j]*ans%MOD;
out.println(dp2[(h*w-1)%2][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;
}
new Main(h,w,b);
/*
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;
}
}
}