SRM 644 div1 easy:OkonomiyakiParty

お好み焼き食べたい・・・

問題:お好み焼きをM人の友達で食べる。お好み焼きにはサイズという整数値があって,M人の間でサイズの差がK以下になるようにお好み焼きを選びたい。このような選び方は何通りあるか。

解法:まずソートする。そして,それぞれの整数iについてosize[i]から差がK以下になっている集合を取り出す。iを選択するという条件のもとで残りのお好み焼きをどのように選択するかを求めれば良い。
以下ソースコード

const int MAXN = 64;
const ll MOD = 1e9+7;
ll cmb[MAXN][MAXN];
void init() {
    cmb[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        cmb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1]) % MOD;
        }
    }
}

class OkonomiyakiParty {
public:
    int count(vector <int> osize, int M, int K) {
        init();
        sort(osize.begin(), osize.end());
        int n = osize.size();
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            int cur = i+M-1;
            if (cur >= n) break;
            while (1) {
                if (osize[cur]-osize[i] > K || cur >= n) break;
                cur++;
            }
            ans += cmb[cur-i-1][M-1];
            ans %= MOD;
        }
        return (int)ans;
    }
};