結果

問題 No.420 mod2漸化式
ユーザー Grenache
提出日時 2016-09-09 23:46:40
言語 Java
(openjdk 23)
結果
AC  
実行時間 152 ms / 1,000 ms
コード長 3,627 bytes
コンパイル時間 4,161 ms
コンパイル使用メモリ 79,168 KB
実行使用メモリ 42,344 KB
最終ジャッジ日時 2024-12-24 11:19:10
合計ジャッジ時間 10,084 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.*;
import java.util.*;
public class Main_yukicoder420 {
    private static Scanner sc;
    private static Printer pr;
    private static void solve() {
        int x = sc.nextInt();
        PC pc = new PC(31, Integer.MAX_VALUE);
        if (x > 31) {
            pr.printf("%d %d\n", 0, 0);
        } else if (x == 0) {
            pr.printf("%d %d\n", 1, 0);
        } else if (x == 31) {
            long ret = (0x1L << 31) - 1;
            pr.printf("%d %d\n", 1, ret);
        } else {
            long ret = 0;
            long tmp = pc.C(31, x) / 31;
//          for (int i = 0; i < 31; i++) {
//              ret += (0x1L << i) * tmp;
//          }
            ret = ((0x1L << 31) - 1) * tmp * x;
            pr.printf("%d %d\n", pc.C(31, x), ret);
        }
    }
    // ---------------------------------------------------
    public static void main(String[] args) {
        sc = new Scanner(System.in);
        pr = new Printer(System.out);
        solve();
        pr.close();
        sc.close();
    }
    @SuppressWarnings("unused")
    private static class PC {
        // MOD must be prime number.
        int MOD;
        // fact[i] : i! % MOD
        long[] fact;
        // ifact[i] : 1/i! % MOD
        long[] ifact;
        PC(int size, int MOD) {
            // O(size)
            // n=sizeまでのnCrを求める。
            // nHrはn+r-1Crになってしまうので注意
            this.MOD = MOD;
            fact = new long[size + 1];
            fact[0] = 1;
            for (int i = 1; i <= size; i++) {
                fact[i] = fact[i - 1] * i % MOD;
            }
            ifact = new long[size + 1];
            int loop = MOD - 2;
            long x = fact[size];
            ifact[size] = 1;
            while (loop > 0) {
                if (loop % 2 == 1) {
                    ifact[size] = ifact[size] * x % MOD;
                }
                x = x * x % MOD;
                loop /= 2;
            }
            for (int i = size - 1; i >= 0; i--) {
                ifact[i] = ifact[i + 1] * (i + 1) % MOD;
            }
        }
        // 組合せの数
        int C(int n, int r) {
            if (r > n) {
                return 0;
            }
            return (int)(((fact[n] * ifact[n - r]) % MOD) * ifact[r] % MOD);
        }
        // 順列
        int P(int n, int r) {
            if (r > n) {
                return 0;
            }
            return (int)((fact[n] * ifact[n -r]) % MOD);
        }
        // 重複組み合わせ
        // 異なるn種のものから重複を許してr個を選ぶ場合の数
        // 0個の種類もあり得る
        int H(int n, int r) {
            if (n == 0 && r == 0) {
                return 1;
            }
            return C(n + r - 1, r);
        }
        // 組合せの数(nが大きいとき)
        //   O(r)で求めることができる。rはsizeの大きさまで
        int C2(long n, int r) {
            long ret = ifact[r];
            for (int i = 1; i <= r; i++) {
                long tmp = (n - r + i) % MOD;
                ret = (ret * tmp) % MOD;
            }
            return (int)ret;
        }
        // 第2種スターリング数
        // n人をちょうどr個のグループに分ける(グループの区別はなし)
        // グループの区別をする場合はr!S(n,r)。全射の場合の数と同義
        // O(r log n)
        int S(long n, int r) {
            //全射の場合の数を包除原理を使って求めて、1/r!をかける。
            long ret = 0;
            for (int i = 1; i <= r; i++) {
                long tmp = (r - i) % 2 == 0 ? 1 : -1;
                tmp *= pow(i, n) * C(r, i) % MOD;
                ret = (ret + tmp + MOD) % MOD;
            }
            ret = ret * ifact[r] % MOD;
            return (int)ret;
        }
        long pow(int a, long n) {
            long loop = n;
            long ret = 1;
            long x = a;
            while (loop > 0) {
                if (loop % 2 == 1) {
                    ret = ret * x % MOD;
                }
                x = x * x % MOD;
                loop /= 2;
            }
            return ret;
        }
    }
    private static class Printer extends PrintWriter {
        Printer(PrintStream out) {
            super(out);
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0