Hatena::Grouptopcoder

yambe2002の日記

 | 

2016-02-06

SRM656 Div2 Hard: PermutationCountsDiv2(練習)

12:25

1~Nの重複のない数字の並べ方の組み合わせ数を求める。

並び替えた数字の列は、必ず以下のルールに従う。

  • 基本的に、前の数字よりも小さくなる
  • ただし、該当数字に位置がpos[]に含まれているときは、その数字は次の数字より小さくなる

[l, r)の範囲について、上記を満たす組み合わせ数を求める関数を、GetCombination(int l, int r)とする。

ある範囲内に、谷になる位置が1つだけあると仮定すると、その位置は必ず最小の値がはいる。

谷の両脇に値を入れるパターン数が、NCRで求めることができる。

(今の数-1から、谷の片側の数を選ぶパターン数になる)

谷がたくさんあるときは、分割して再帰的にGetCombination()を呼べばよい。


最初、dp[]をintで宣言してオーバーフローしてしまっていた。


public class NCR
{
    long[,] ncr;

    public NCR(int size, int MOD)
    {
        ncr = new long[size + 1, size + 1];
        for (int i = 0; i <= size; i++)
        {
            ncr[i, 0] = 1;
            for (int j = 1; j <= i; j++)
            {
                ncr[i, j] = (ncr[i - 1, j] + ncr[i - 1, j - 1]) % MOD;
            }
        }
    }

    public long GetNcr(int n, int r)
    {
        return ncr[n, r];
    }
}

public class PermutationCountsDiv2 {
    int MOD = 1000000007;

    NCR ncr;
    int N;
    bool[] lessThanNext;
    long[,] dp;    //int[]だとオーバーフローする

    bool IsLowest(int idx, int l, int r)
    {
        return (idx == l || !lessThanNext[idx - 1]) && (idx == r - 1 || lessThanNext[idx]);
    }

    int[] GetLowestPositions(int l, int r)
    {
        var ret = new List<int>();

        for (int idx = l; idx < r; idx++)
            if (IsLowest(idx, l, r)) ret.Add(idx);

        return ret.ToArray();
    }

    //return combination num of [l r)
    long GetCombination(int l, int r)
    {
        if (dp[l, r] != 0) return dp[l, r];

        long ret = 0;
        var lowestPositions = GetLowestPositions(l, r);

        foreach (var lowestPos in lowestPositions)
        {
            var cmb = lowestPos == l || lowestPos == r - 1 ? 1 : ncr.GetNcr(r - l - 1, lowestPos - l);
            ret += (((GetCombination(l, lowestPos) * GetCombination(lowestPos + 1, r)) % MOD) * cmb) % MOD;
            ret %= MOD;
        }

        dp[l, r] = ret % MOD;
        return dp[l, r];
    }

    public int countPermutations(int pN, int[] pos) 
    {
        N = pN;
        
        lessThanNext = new bool[N + 1];
        foreach (var p in pos) lessThanNext[p - 1] = true;

        ncr = new NCR(N + 2, MOD);
        dp = new long[N + 1, N + 1];

        for (int l = 0; l <= N; l++)
        {
            dp[l, l] = 1;
            if (l <= N - 1) dp[l, l + 1] = 1;
        }

        return (int)GetCombination(0, N);
    }
}
 |