結果
| 問題 |
No.2802 Pill Bug in Grid Maze
|
| ユーザー |
 宇宙猫
|
| 提出日時 | 2024-07-12 10:19:51 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,120 ms / 2,000 ms |
| コード長 | 15,839 bytes |
| コンパイル時間 | 4,113 ms |
| コンパイル使用メモリ | 89,400 KB |
| 実行使用メモリ | 46,308 KB |
| 最終ジャッジ日時 | 2024-07-12 10:20:24 |
| 合計ジャッジ時間 | 30,940 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 31 |
ソースコード
// Language: Java 17
// Encoding: UTF-8
import java.util.Scanner;
/**
* Good Luck, Have Fun.
*/
public class Main {
static Scanner scanner = new Scanner(System.in);
static int readInt() {return scanner.nextInt();}
static int[] readInts(int len) {int[] a=new int[len];for(int i=0;i<len;i++)a[i]=readInt();return a;}
static long readLong() {return scanner.nextLong();}
static String readString() {return scanner.next();}
public static void main(String[] args) throws Exception {
int h = readInt();
int w = readInt();
int mod=998244353;
if (h==1 || w==1) {
System.out.println(1);
return;
}
int[] factory = new int[500000];
int[] factory_inv = new int[500000];
factory[0]=1;
for (int i=1;i<factory.length;i++)
factory[i]=(int)((long)i*factory[i-1]%mod);
for (int i=0;i<factory_inv.length;i++)
factory_inv[i]=(int)Mod.modInv(factory[i], mod);
long sum=0;
for (int turn=1;;turn++) {
int r_fix=turn>>1;
int d_fix=(turn+1)>>1;
int r_left=w-1-r_fix;
int d_left=h-1-d_fix;
int r_dest=(turn>>1)+1;
int d_dest=(turn+1)>>1;
if (r_left<0 || d_left<0) break;
long pattern=(long)factory[r_left+r_dest-1]
*factory_inv[r_left]%mod
*factory_inv[r_dest-1]%mod;
pattern=pattern*factory[d_left+d_dest-1]%mod
*factory_inv[d_left]%mod
*factory_inv[d_dest-1]%mod;
int fixed = h+w-1+turn-1;
long flex = (long)h*w-fixed;
long _2xp = Mod.modPow2(flex, mod);
sum=(sum+pattern*_2xp%mod)%mod;
}
System.out.println(sum);
}
}
/**
* つかいかた
* 1. 型の扱いが面倒なので宣言はvarでやろう！
* 2. 引数の数はコンパイル時にいい感じに処理してくれるぞ！
* 3. オーバーヘッドとはおさらば！
* (C) MIT License - 2024 GalaxyCat42
*/
@SuppressWarnings("unused")
abstract class IntArray {
public final int[] ref;
protected IntArray(int size) {
this.ref = new int[size];
}
public void fill(int value) {
if (ref.length == 0) return;
ref[0]=value;
for (int len=1;len<ref.length;len*=2)
System.arraycopy(ref, 0, ref, len, Math.min(len, ref.length-len));
}
public void read(Scanner scanner) {
for (int i=0;i<ref.length;i++)
ref[i]=scanner.nextInt();
}
protected static int validateLen(int ... lens) {
if (lens == null || lens.length == 0)
throw new IllegalArgumentException("You cannot create zero-dimensional array");
long len = 1;
for (int l : lens) {
if (l<0) throw new IllegalArgumentException("Size is Negative");
len*=l;
// ここにSOFT_MAX_ARRAY_LENGTHを入れたかった
if (Integer.MAX_VALUE<len)
throw new IllegalArgumentException("Overflow");
}
return (int) len;
}
protected static int validate(int i, int len) {
if (i<0 || len<=i)
throw new ArrayIndexOutOfBoundsException(i+" in "+len);
return i;
}
// 自動生成クラス
/** 次数1ならわざわざ多次元配列にするなというのが本音だが、fillなんかはこっちが速い。 */
public static final class $D1 extends IntArray {private final int n;private $D1(int n){super(validateLen(n));this.n=n;}public int idx(int a){return validate(a,n);}}
public static final class $D2 extends IntArray {private final int n,o;private $D2(int n, int o){super(validateLen(n,o));this.n=n;this.o=o;}public int idx(int a, int b){return validate(a,n)*o+validate(b,o);}}
public static final class $D3 extends IntArray {private final int n,o,p;private $D3(int n, int o, int p){super(validateLen(n,o,p));this.n=n;this.o=o;this.p=p;}public int idx(int a, int b, int c){return validate(a,n)*o*p+validate(b,o)*p+validate(c,p);}}
public static final class $D4 extends IntArray {private final int n,o,p,q;private $D4(int n, int o, int p, int q){super(validateLen(n,o,p,q));this.n=n;this.o=o;this.p=p;this.q=q;}public int idx(int a, int b, int c, int d){return validate(a,n)*o*p*q+validate(b,o)*p*q+validate(c,p)*q+validate(d,q);}}
public static final class $D5 extends IntArray {private final int n,o,p,q,r;private $D5(int n, int o, int p, int q, int r){super(validateLen(n,o,p,q,r));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;}public int idx(int a, int b, int c, int d, int e){return validate(a,n)*o*p*q*r+validate(b,o)*p*q*r+validate(c,p)*q*r+validate(d,q)*r+validate(e,r);}}
public static final class $D6 extends IntArray {private final int n,o,p,q,r,s;private $D6(int n, int o, int p, int q, int r, int s){super(validateLen(n,o,p,q,r,s));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;}public int idx(int a, int b, int c, int d, int e, int f){return validate(a,n)*o*p*q*r*s+validate(b,o)*p*q*r*s+validate(c,p)*q*r*s+validate(d,q)*r*s+validate(e,r)*s+validate(f,s);}}
public static final class $D7 extends IntArray {private final int n,o,p,q,r,s,t;private $D7(int n, int o, int p, int q, int r, int s, int t){super(validateLen(n,o,p,q,r,s,t));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;}public int idx(int a, int b, int c, int d, int e, int f, int g){return validate(a,n)*o*p*q*r*s*t+validate(b,o)*p*q*r*s*t+validate(c,p)*q*r*s*t+validate(d,q)*r*s*t+validate(e,r)*s*t+validate(f,s)*t+validate(g,t);}}
public static final class $D8 extends IntArray {private final int n,o,p,q,r,s,t,u;private $D8(int n, int o, int p, int q, int r, int s, int t, int u){super(validateLen(n,o,p,q,r,s,t,u));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;this.u=u;}public int idx(int a, int b, int c, int d, int e, int f, int g, int h){return validate(a,n)*o*p*q*r*s*t*u+validate(b,o)*p*q*r*s*t*u+validate(c,p)*q*r*s*t*u+validate(d,q)*r*s*t*u+validate(e,r)*s*t*u+validate(f,s)*t*u+validate(g,t)*u+validate(h,u);}}
public static final class $D9 extends IntArray {private final int n,o,p,q,r,s,t,u,v;private $D9(int n, int o, int p, int q, int r, int s, int t, int u, int v){super(validateLen(n,o,p,q,r,s,t,u,v));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;this.u=u;this.v=v;}public int idx(int a, int b, int c, int d, int e, int f, int g, int h, int i){return validate(a,n)*o*p*q*r*s*t*u*v+validate(b,o)*p*q*r*s*t*u*v+validate(c,p)*q*r*s*t*u*v+validate(d,q)*r*s*t*u*v+validate(e,r)*s*t*u*v+validate(f,s)*t*u*v+validate(g,t)*u*v+validate(h,u)*v+validate(i,v);}}
public static final class DN extends IntArray {
private final int[] lens;
private DN(int ... lens) {
super(IntArray.validateLen(lens));
this.lens = lens.clone();
}
public int idx(int ... is) {
if (is == null || is.length != lens.length)
throw new IllegalArgumentException(":(");
int base=1;
int index=0;
for (int i=lens.length;0<i--;) {
validate(is[i], lens[i]);
index+=base*is[i];
}
return index;
}
}
public static IntArray.$D1 of(int o){return new IntArray.$D1(o);}
public static IntArray.$D2 of(int o, int p){return new IntArray.$D2(o,p);}
public static IntArray.$D3 of(int o, int p, int q){return new IntArray.$D3(o,p,q);}
public static IntArray.$D4 of(int o, int p, int q, int r){return new IntArray.$D4(o,p,q,r);}
public static IntArray.$D5 of(int o, int p, int q, int r, int s){return new IntArray.$D5(o,p,q,r,s);}
public static IntArray.$D6 of(int o, int p, int q, int r, int s, int t){return new IntArray.$D6(o,p,q,r,s,t);}
public static IntArray.$D7 of(int o, int p, int q, int r, int s, int t, int u){return new IntArray.$D7(o,p,q,r,s,t,u);}
public static IntArray.$D8 of(int o, int p, int q, int r, int s, int t, int u, int v){return new IntArray.$D8(o,p,q,r,s,t,u,v);}
public static IntArray.$D9 of(int o, int p, int q, int r, int s, int t, int u, int v, int w){return new IntArray.$D9(o,p,q,r,s,t,u,v,w);}
public static void of() {
throw new IllegalArgumentException("You shouldn't do this");
}
public static IntArray.DN of(int ... lens) {
return new IntArray.DN(lens);
}
}
/**
* つかいかた
* 1. 型の扱いが面倒なので宣言はvarでやろう！
* 2. 引数の数はコンパイル時にいい感じに処理してくれるぞ！
* 3. オーバーヘッドとはおさらば！
* (C) MIT License - 2024 GalaxyCat42
*/
@SuppressWarnings("unused")
abstract class LongArray {
public final long[] ref;
protected LongArray(int size) {
this.ref = new long[size];
}
public void fill(int value) {
if (ref.length == 0) return;
ref[0]=value;
for (int len=1;len<ref.length;len*=2)
System.arraycopy(ref, 0, ref, len, Math.min(len, ref.length-len));
}
public void read(Scanner scanner) {
for (int i=0;i<ref.length;i++)
ref[i]=scanner.nextInt();
}
protected static int validateLen(int ... lens) {
if (lens == null || lens.length == 0)
throw new IllegalArgumentException("You cannot create zero-dimensional array");
long len = 1;
for (int l : lens) {
if (l<0) throw new IllegalArgumentException("Size is Negative");
len*=l;
// ここにSOFT_MAX_ARRAY_LENGTHを入れたかった
if (Integer.MAX_VALUE<len)
throw new IllegalArgumentException("Overflow");
}
return (int) len;
}
protected static int validate(int i, int len) {
if (i<0 || len<=i)
throw new ArrayIndexOutOfBoundsException(i+" in "+len);
return i;
}
// 自動生成クラス
/** 次数1ならわざわざ多次元配列にするなというのが本音だが、fillなんかはこっちが速い。 */
public static final class $D1 extends LongArray {private final int n;private $D1(int n){super(validateLen(n));this.n=n;}public int idx(int a){return validate(a,n);}}
public static final class $D2 extends LongArray {private final int n,o;private $D2(int n, int o){super(validateLen(n,o));this.n=n;this.o=o;}public int idx(int a, int b){return validate(a,n)*o+validate(b,o);}}
public static final class $D3 extends LongArray {private final int n,o,p;private $D3(int n, int o, int p){super(validateLen(n,o,p));this.n=n;this.o=o;this.p=p;}public int idx(int a, int b, int c){return validate(a,n)*o*p+validate(b,o)*p+validate(c,p);}}
public static final class $D4 extends LongArray {private final int n,o,p,q;private $D4(int n, int o, int p, int q){super(validateLen(n,o,p,q));this.n=n;this.o=o;this.p=p;this.q=q;}public int idx(int a, int b, int c, int d){return validate(a,n)*o*p*q+validate(b,o)*p*q+validate(c,p)*q+validate(d,q);}}
public static final class $D5 extends LongArray {private final int n,o,p,q,r;private $D5(int n, int o, int p, int q, int r){super(validateLen(n,o,p,q,r));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;}public int idx(int a, int b, int c, int d, int e){return validate(a,n)*o*p*q*r+validate(b,o)*p*q*r+validate(c,p)*q*r+validate(d,q)*r+validate(e,r);}}
public static final class $D6 extends LongArray {private final int n,o,p,q,r,s;private $D6(int n, int o, int p, int q, int r, int s){super(validateLen(n,o,p,q,r,s));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;}public int idx(int a, int b, int c, int d, int e, int f){return validate(a,n)*o*p*q*r*s+validate(b,o)*p*q*r*s+validate(c,p)*q*r*s+validate(d,q)*r*s+validate(e,r)*s+validate(f,s);}}
public static final class $D7 extends LongArray {private final int n,o,p,q,r,s,t;private $D7(int n, int o, int p, int q, int r, int s, int t){super(validateLen(n,o,p,q,r,s,t));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;}public int idx(int a, int b, int c, int d, int e, int f, int g){return validate(a,n)*o*p*q*r*s*t+validate(b,o)*p*q*r*s*t+validate(c,p)*q*r*s*t+validate(d,q)*r*s*t+validate(e,r)*s*t+validate(f,s)*t+validate(g,t);}}
public static final class $D8 extends LongArray {private final int n,o,p,q,r,s,t,u;private $D8(int n, int o, int p, int q, int r, int s, int t, int u){super(validateLen(n,o,p,q,r,s,t,u));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;this.u=u;}public int idx(int a, int b, int c, int d, int e, int f, int g, int h){return validate(a,n)*o*p*q*r*s*t*u+validate(b,o)*p*q*r*s*t*u+validate(c,p)*q*r*s*t*u+validate(d,q)*r*s*t*u+validate(e,r)*s*t*u+validate(f,s)*t*u+validate(g,t)*u+validate(h,u);}}
public static final class $D9 extends LongArray {private final int n,o,p,q,r,s,t,u,v;private $D9(int n, int o, int p, int q, int r, int s, int t, int u, int v){super(validateLen(n,o,p,q,r,s,t,u,v));this.n=n;this.o=o;this.p=p;this.q=q;this.r=r;this.s=s;this.t=t;this.u=u;this.v=v;}public int idx(int a, int b, int c, int d, int e, int f, int g, int h, int i){return validate(a,n)*o*p*q*r*s*t*u*v+validate(b,o)*p*q*r*s*t*u*v+validate(c,p)*q*r*s*t*u*v+validate(d,q)*r*s*t*u*v+validate(e,r)*s*t*u*v+validate(f,s)*t*u*v+validate(g,t)*u*v+validate(h,u)*v+validate(i,v);}}
public static final class DN extends LongArray {
private final int[] lens;
private DN(int ... lens) {
super(IntArray.validateLen(lens));
this.lens = lens.clone();
}
public int idx(int ... is) {
if (is == null || is.length != lens.length)
throw new IllegalArgumentException(":(");
int base=1;
int index=0;
for (int i=lens.length;0<i--;) {
validate(is[i], lens[i]);
index+=base*is[i];
}
return index;
}
}
public static LongArray.$D1 of(int o){return new LongArray.$D1(o);}
public static LongArray.$D2 of(int o, int p){return new LongArray.$D2(o,p);}
public static LongArray.$D3 of(int o, int p, int q){return new LongArray.$D3(o,p,q);}
public static LongArray.$D4 of(int o, int p, int q, int r){return new LongArray.$D4(o,p,q,r);}
public static LongArray.$D5 of(int o, int p, int q, int r, int s){return new LongArray.$D5(o,p,q,r,s);}
public static LongArray.$D6 of(int o, int p, int q, int r, int s, int t){return new LongArray.$D6(o,p,q,r,s,t);}
public static LongArray.$D7 of(int o, int p, int q, int r, int s, int t, int u){return new LongArray.$D7(o,p,q,r,s,t,u);}
public static LongArray.$D8 of(int o, int p, int q, int r, int s, int t, int u, int v){return new LongArray.$D8(o,p,q,r,s,t,u,v);}
public static LongArray.$D9 of(int o, int p, int q, int r, int s, int t, int u, int v, int w){return new LongArray.$D9(o,p,q,r,s,t,u,v,w);}
public static void of() {
throw new IllegalArgumentException("You shouldn't do this");
}
public static LongArray.DN of(int ... lens) {
return new LongArray.DN(lens);
}
}
class Mod {
private Mod() {
throw new UnsupportedOperationException();
}
static long modPow(long x, long a, long mod) {
if (a == 1) return x;
if ((a&1) != 0) return (x * modPow(x, a-1, mod))%mod;
long t = modPow(x, a>>1, mod);
return (t*t)%mod;
}
static long modPow2(long a, long mod) {
if (a <= 1) return a==1?2:a==0?1:0;
if ((a&1) != 0) return (modPow2(a-1, mod)<<1)%mod;
long t = modPow2(a>>1, mod);
return (t*t)%mod;
}
static long modInv(long x, long mod) {
return modPow(x, mod-2, mod);
}
static long modFrac(long a, long b, long mod) {
return modInv(b, mod) * a % mod;
}
}