na_o_ysのブログ

プログラミングなど

(unrated) SRM 644 Div1 Easy, OkonomiyakiParty

問題

N (< 50) 種類のお好み焼きがある. i 番目の大きさは配列 osize[i] (< 10000) で与えられる. このうち M (< N) 種類を選ぶときに, 最も小さいものと最も大きいものの差が K 以下となるような選び方は何通りあるか, 1,000,000,007 の剰余で求めよ.

方針

昇順でソートし, 最も小さいお好み焼きを i としたときの選び方を数え上げる.

解答

using ll = long long;
const int MOD = 1000000007;

class OkonomiyakiParty
{
public:
    int count(vector <int> osize, int M, int K) {
        fill(memo[0], memo[59]+60, -1);
        int N = osize.size();
        sort(all(osize));
        ll ans = 0;
        loop (N, i) {
            int j = i+1;
            while (j < N && osize[j]-osize[i] <= K) j++;
            ans = (ans + cmb(j-i-1, M-1)) % MOD;
        }
        return ans;
    }

    ll memo[60][60];
    ll cmb(ll n, ll r) {
        if (n < 0 || r < 0 || n < r) return 0;
        if (memo[n][r] != -1) return memo[n][r];
        if (!r) return 1;
        return memo[n][r] = (cmb(n-1, r-1) + cmb(n-1, r)) % MOD;
    }
};