結果

問題 No.1741 Arrays and XOR Procedure
ユーザー ks2m
提出日時 2021-11-12 22:18:07
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,795 bytes
コンパイル時間 2,514 ms
コンパイル使用メモリ 76,656 KB
実行使用メモリ 67,776 KB
最終ジャッジ日時 2024-11-25 19:15:39
合計ジャッジ時間 12,279 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();
        int mod = 998244353;
        Kaijou kai = new Kaijou(n, mod);
        Kaijou2 kai2 = new Kaijou2(n, 2);
        int n1 = n - 1;
        int a = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < n; i++) {
            long v = kai2.comb(n1, i);
            if (v % 2 == 1) {
                if (b[i] == 1) {
                    a++;
                } else if (b[i] == -1) {
                    x++;
                }
            }
            if (b[i] == -1) {
                y++;
            }
        }
        long ans = 0;
        if (a == 0) {
            for (int i = 1; i <= x; i += 2) {
                ans += kai.comb(x, i);
            }
        } else {
            for (int i = 0; i <= x; i += 2) {
                ans += kai.comb(x, i);
            }
        }
        ans %= mod;
        ans *= power(2, y - x, mod);
        ans %= mod;
        System.out.println(ans);
    }
    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
    static class Kaijou {
        long[] p, pi;
        int m;
        public Kaijou(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * i % m;
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * i % m;
            }
        }
        public long comb(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }
        public long perm(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[n - r] % m;
        }
    }
    static class Kaijou2 {
        long[] p, pi;
        int[] im, cm;
        int m;
        public Kaijou2(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            im = new int[n];
            cm = new int[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                int i2 = i;
                while (i2 % m == 0) {
                    cm[i]++;
                    i2 /= m;
                }
                p[i] = p[i - 1] * i2 % m;
                im[i] = i2;
                cm[i] += cm[i - 1];
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * im[i] % m;
            }
        }
        public long comb(int n, int r) {
            if (n < r) return 0;
            if (cm[n] > cm[r] + cm[n - r]) {
                return 0;
            }
            return p[n] * pi[r] % m * pi[n - r] % m;
        }
        public long perm(int n, int r) {
            if (n < r) return 0;
            if (cm[n] > cm[n - r]) {
                return 0;
            }
            return p[n] * pi[n - r] % m;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0