結果

問題 No.411 昇順昇順ソート
ユーザー りあん
提出日時 2016-08-12 22:53:15
言語 C#
(csc 3.100.19.26603)
結果
AC  
実行時間 1,243 ms
コード長 6,369 Byte
コンパイル時間 1,310 ms
使用メモリ 307,324 KB
最終ジャッジ日時 2019-10-08 20:10:00

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
gen_case1.txt AC 35 ms
16,608 KB
gen_case2.txt AC 35 ms
16,612 KB
gen_case3.txt AC 36 ms
18,656 KB
gen_case4.txt AC 35 ms
16,608 KB
gen_case5.txt AC 35 ms
18,656 KB
gen_case6.txt AC 35 ms
18,656 KB
gen_case7.txt AC 35 ms
14,572 KB
gen_case8.txt AC 34 ms
14,568 KB
gen_case9.txt AC 35 ms
18,652 KB
gen_case10.txt AC 37 ms
16,612 KB
gen_case11.txt AC 35 ms
16,608 KB
gen_case12.txt AC 35 ms
16,604 KB
gen_case13.txt AC 36 ms
14,580 KB
gen_case14.txt AC 36 ms
14,576 KB
gen_case15.txt AC 34 ms
14,576 KB
gen_case16.txt AC 35 ms
14,560 KB
gen_case17.txt AC 35 ms
16,604 KB
gen_case18.txt AC 34 ms
16,608 KB
gen_case19.txt AC 34 ms
14,552 KB
gen_case20.txt AC 35 ms
18,656 KB
sample1.txt AC 35 ms
16,604 KB
sample2.txt AC 35 ms
16,620 KB
sample3.txt AC 35 ms
16,604 KB
sample4.txt AC 35 ms
18,660 KB
test1.txt AC 35 ms
16,612 KB
test2.txt AC 34 ms
14,580 KB
test3.txt AC 34 ms
16,604 KB
test4.txt AC 40 ms
18,660 KB
test5.txt AC 1,218 ms
301,164 KB
test6.txt AC 607 ms
164,912 KB
test7.txt AC 1,207 ms
303,240 KB
test8.txt AC 1,212 ms
299,200 KB
test9.txt AC 1,243 ms
307,324 KB
test10.txt AC 1,223 ms
305,280 KB
テストケース一括ダウンロード
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.100.19.26603 (9d80dea7)
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