結果

問題 No.411 昇順昇順ソート
ユーザー りあん
提出日時 2016-08-12 22:53:15
言語 C#
(csc 2.8.2.62916)
結果
AC  
実行時間 1,309 ms
コード長 6,369 Byte
コンパイル時間 698 ms
使用メモリ 293,880 KB
最終ジャッジ日時 2019-07-11 13:09:21

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
gen_case1.txt AC 28 ms
9,544 KB
gen_case2.txt AC 27 ms
9,540 KB
gen_case3.txt AC 28 ms
9,548 KB
gen_case4.txt AC 28 ms
9,540 KB
gen_case5.txt AC 28 ms
9,544 KB
gen_case6.txt AC 28 ms
9,540 KB
gen_case7.txt AC 28 ms
9,544 KB
gen_case8.txt AC 28 ms
9,544 KB
gen_case9.txt AC 28 ms
9,536 KB
gen_case10.txt AC 28 ms
9,544 KB
gen_case11.txt AC 28 ms
9,540 KB
gen_case12.txt AC 27 ms
9,548 KB
gen_case13.txt AC 27 ms
9,544 KB
gen_case14.txt AC 28 ms
9,536 KB
gen_case15.txt AC 27 ms
9,536 KB
gen_case16.txt AC 29 ms
9,540 KB
gen_case17.txt AC 29 ms
9,536 KB
gen_case18.txt AC 28 ms
9,536 KB
gen_case19.txt AC 28 ms
9,544 KB
gen_case20.txt AC 29 ms
9,540 KB
sample1.txt AC 28 ms
9,520 KB
sample2.txt AC 28 ms
9,528 KB
sample3.txt AC 30 ms
9,524 KB
sample4.txt AC 28 ms
9,516 KB
test1.txt AC 28 ms
9,536 KB
test2.txt AC 28 ms
9,532 KB
test3.txt AC 29 ms
9,532 KB
test4.txt AC 35 ms
12,384 KB
test5.txt AC 1,281 ms
293,864 KB
test6.txt AC 628 ms
153,476 KB
test7.txt AC 1,309 ms
293,880 KB
test8.txt AC 1,309 ms
293,868 KB
test9.txt AC 1,298 ms
293,864 KB
test10.txt AC 1,279 ms
293,860 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 2.8.2.62916 (2ad4aabc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Program
{
    const int M = 1000000007;
    const double eps = 1e-9;
    static int[] dd = { 0, 1, 0, -1, 0 };
    static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        var sc = new Scan();
        int n, k;
        sc.Multi(out n, out k);
        int m = 1 << n;
        var dp0 = new int[m][];
        var dp1 = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp0[i] = new int[n];
            dp1[i] = new int[n];
        }
        dp0[1 << (k - 1)][k - 1] = 1;
        var zsum = new int[n + 1];
        var osum = new int[n + 1];
        for (int i = 0; i < m; i++)
        {
            zsum[0] = 0;
            osum[0] = 0;
            for (int j = 0; j < n; j++)
            {
                zsum[j + 1] = zsum[j];
                osum[j + 1] = osum[j];
                if (((i >> j) & 1) == 1)
                {
                    zsum[j + 1] += dp0[i][j];
                    osum[j + 1] += dp1[i][j];
                }
            }
            for (int j = 0; j < n; j++)
            {
                if (((i >> j) & 1) == 0)
                {
                    dp0[i + (1 << j)][j] += zsum[j];
                    dp1[i + (1 << j)][j] += osum[j];
                    dp1[i + (1 << j)][j] += zsum[n] - zsum[j + 1];                    
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += dp1[m - 1][i];
        }
        sw.WriteLine(ans);
        sw.Flush();
    }

    static void swap<T>(ref T a, ref T b) { var t = a; a = b; b = t; }
    static void swap<T>(IList<T> a, int i, int j) { var t = a[i]; a[i] = a[j]; a[j] = a[i]; }
    static T Max<T>(params T[] a) { return a.Max(); }
    static T Min<T>(params T[] a) { return a.Min(); }

    static T[] copy<T>(IList<T> a)
    {
        var ret = new T[a.Count];
        for (int i = 0; i < a.Count; i++) ret[i] = a[i];
        return ret;
    }
}
class Scan
{
    public int Int { get { return int.Parse(Str); } }
    public long Long { get { return long.Parse(Str); } }
    public double Double { get { return double.Parse(Str); } }
    public string Str { get { return Console.ReadLine().Trim(); } }
    public int[] IntArr { get { return StrArr.Select(int.Parse).ToArray(); } }
    public int[] IntArrWithSep(char sep) { return Str.Split(sep).Select(int.Parse).ToArray(); }
    public long[] LongArr { get { return StrArr.Select(long.Parse).ToArray(); } }
    public double[] DoubleArr { get { return StrArr.Select(double.Parse).ToArray(); } }
    public string[] StrArr { get { return Str.Split(); } }
    public void Multi(out int a, out int b) { var arr = IntArr; a = arr[0]; b = arr[1]; }
    public void Multi(out int a, out int b, out int c) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; }
    public void Multi(out int a, out string b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1]; }
    public void Multi(out string a, out int b) { var arr = StrArr; a = arr[0]; b = int.Parse(arr[1]); }
    public void Multi(out int a, out char b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1][0]; }
    public void Multi(out char a, out int b) { var arr = StrArr; a = arr[0][0]; b = int.Parse(arr[1]); }
    public void Multi(out long a, out long b) { var arr = LongArr; a = arr[0]; b = arr[1]; }
    public void Multi(out long a, out int b) { var arr = LongArr; a = arr[0]; b = (int)arr[1]; }
    public void Multi(out int a, out long b) { var arr = LongArr; a = (int)arr[0]; b = arr[1]; }
    public void Multi(out string a, out string b) { var arr = StrArr; a = arr[0]; b = arr[1]; }
}
class mymath
{
    static int Mod = 1000000007;
    public void setMod(int m) { Mod = m; }
    public bool isprime(long a)
    {
        if (a < 2) return false;
        for (long i = 2; i * i <= a; i++) if (a % i == 0) return false;
        return true;
    }
    public long[][] powmat(long[][] A, long n)
    {
        var E = new long[A.Length][];
        for (int i = 0; i < A.Length; i++)
        {
            E[i] = new long[A.Length];
            E[i][i] = 1;
        }
        if (n == 0) return E;
        var t = powmat(A, n / 2);
        if ((n & 1) == 0) return mulmat(t, t);
        return mulmat(mulmat(t, t), A);
    }
    public long[] mulmat(long[][] A, long[] x)
    {
        var ans = new long[A.Length];
        for (int i = 0; i < A.Length; i++) for (int j = 0; j < x.Length; j++) ans[i] = (ans[i] + x[j] * A[i][j]) % Mod;
        return ans;
    }
    public long[][] mulmat(long[][] A, long[][] B)
    {
        var ans = new long[A.Length][];
        for (int i = 0; i < A.Length; i++)
        {
            ans[i] = new long[B[0].Length];
            for (int j = 0; j < B[0].Length; j++) for (int k = 0; k < B.Length; k++) ans[i][j] = (ans[i][j] + A[i][k] * B[k][j]) % Mod;
        }
        return ans;
    }
    public long powmod(long a, long b)
    {
        if (a >= Mod) return powmod(a % Mod, b);
        if (a == 0) return 0;
        if (b == 0) return 1;
        var t = powmod(a, b / 2);
        if ((b & 1) == 0) return t * t % Mod;
        return t * t % Mod * a % Mod;
    }
    public long gcd(long a, long b)
    {
        while (b > 0) { var t = a % b; a = b; b = t; }
        return a;
    }
    public long lcm(long a, long b) { return a * (b / gcd(a, b)); }
    public long Comb(int n, int r)
    {
        if (n < 0 || r < 0 || r > n) return 0;
        if (n - r < r) r = n - r;
        if (r == 0) return 1;
        if (r == 1) return n;
        var numerator = new int[r];
        var denominator = new int[r];
        for (int k = 0; k < r; k++)
        {
            numerator[k] = n - r + k + 1;
            denominator[k] = k + 1;
        }
        for (int p = 2; p <= r; p++)
        {
            int pivot = denominator[p - 1];
            if (pivot > 1)
            {
                int offset = (n - r) % p;
                for (int k = p - 1; k < r; k += p)
                {
                    numerator[k - offset] /= pivot;
                    denominator[k] /= pivot;
                }
            }
        }
        long result = 1;
        for (int k = 0; k < r; k++) if (numerator[k] > 1) result = result * numerator[k] % Mod;
        return result;
    }
}
0