#993779 (Java21) No.2802 Pill Bug in Grid Maze

提出ソース
結果

問題	No.2802 Pill Bug in Grid Maze
ユーザー	宇宙猫
提出日時	2024-07-12 10:17:12
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	15,832 bytes
コンパイル時間	4,960 ms
コンパイル使用メモリ	90,520 KB
実行使用メモリ	61,152 KB
最終ジャッジ日時	2024-07-12 10:17:45
合計ジャッジ時間	31,731 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	685 ms 46,020 KB
testcase_01	AC	139 ms 41,116 KB
testcase_02	AC	685 ms 46,348 KB
testcase_03	AC	694 ms 46,300 KB
testcase_04	AC	683 ms 46,212 KB
testcase_05	AC	687 ms 46,208 KB
testcase_06	AC	137 ms 41,172 KB
testcase_07	AC	137 ms 41,472 KB
testcase_08	WA	-
testcase_09	AC	135 ms 41,156 KB
testcase_10	AC	694 ms 46,008 KB
testcase_11	AC	683 ms 46,108 KB
testcase_12	AC	690 ms 46,272 KB
testcase_13	AC	686 ms 46,144 KB
testcase_14	AC	713 ms 46,060 KB
testcase_15	AC	707 ms 46,264 KB
testcase_16	AC	719 ms 46,188 KB
testcase_17	AC	722 ms 46,080 KB
testcase_18	AC	736 ms 46,156 KB
testcase_19	AC	712 ms 46,036 KB
testcase_20	WA	-
testcase_21	AC	741 ms 46,072 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	708 ms 46,172 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 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;
            int flex = 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;
    }

}
yukicoder

結果

テストケース

ソースコード
