結果

問題 No.2802 Pill Bug in Grid Maze
ユーザー 宇宙猫宇宙猫
提出日時 2024-07-12 10:19:51
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 684 ms
46,076 KB
testcase_01 AC 136 ms
41,248 KB
testcase_02 AC 685 ms
46,116 KB
testcase_03 AC 689 ms
46,180 KB
testcase_04 AC 703 ms
46,308 KB
testcase_05 AC 689 ms
46,308 KB
testcase_06 AC 136 ms
41,104 KB
testcase_07 AC 138 ms
41,164 KB
testcase_08 AC 1,120 ms
46,084 KB
testcase_09 AC 137 ms
41,212 KB
testcase_10 AC 687 ms
46,236 KB
testcase_11 AC 692 ms
45,928 KB
testcase_12 AC 706 ms
46,076 KB
testcase_13 AC 720 ms
46,012 KB
testcase_14 AC 694 ms
46,252 KB
testcase_15 AC 704 ms
46,188 KB
testcase_16 AC 692 ms
46,224 KB
testcase_17 AC 714 ms
46,132 KB
testcase_18 AC 702 ms
46,016 KB
testcase_19 AC 692 ms
46,156 KB
testcase_20 AC 848 ms
45,932 KB
testcase_21 AC 716 ms
46,008 KB
testcase_22 AC 777 ms
46,132 KB
testcase_23 AC 778 ms
46,100 KB
testcase_24 AC 869 ms
45,984 KB
testcase_25 AC 778 ms
46,072 KB
testcase_26 AC 770 ms
45,908 KB
testcase_27 AC 710 ms
46,168 KB
testcase_28 AC 827 ms
46,244 KB
testcase_29 AC 964 ms
46,200 KB
testcase_30 AC 723 ms
45,996 KB
testcase_31 AC 1,029 ms
46,268 KB
testcase_32 AC 800 ms
46,192 KB
testcase_33 AC 808 ms
46,004 KB
testcase_34 AC 870 ms
46,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
    }

}
0