SRM 644 div 1
あけましておめでとうございます
するめは新年早々、unratedだった
easy
はじめにソートする
尺取りみたいに見て、osize[i]-osize[j]>Kとなった瞬間に(j-i-1)C(M-1)を答えに加算する(osize[i]を最小のお好み焼きとして必ず選ぶときのありえる組合せの数)
組合せの計算はライブラリにしてあったのでコピペするだけだった
#include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; #define IDX(v,a) distance(a.begin(),lower_bound(a.begin(),a.end(),v)) typedef long long ll; const ll MOD = 1000000007; typedef pair<int,int> P; ll mod_pow(ll a, ll n){ ll ret = 1; ll t = a; while(n){ if(n&1) ret = ret * t % MOD; t = t * t % MOD; n >>= 1; } return ret; } ll mod_comb(ll N, ll K){ ll nPk = 1 , kfact = 1; for(ll i = N; i > N - K; i--) nPk = nPk * (i % MOD) % MOD; kfact = 1; for(ll i = 2; i <= K; i++) kfact = kfact * i % MOD; kfact = mod_pow(kfact, MOD - 2); return ((nPk * kfact) % MOD); } class OkonomiyakiParty{ public: int count(vector <int> osize, int M, int K){ int N = osize.size(); ll ans = 0; sort(osize.begin(), osize.end()); int j = 0; for(int i = 0; i < N; i++){ for(j = i+M-1; j < N; j++){ if(osize[j] - osize[i] > K) break; } if(j-i>=M){ ll t = mod_comb(j-i-1,M-1); printf("%d %d c=%lld\n", i,j,t); ans += t; ans %= MOD; } } return (int)ans; } };