【PGBATTLE2020_かつおぶし3】ハンドベル

過去問：https://products.sint.co.jp/q_list_2020
解答コード：https://products.sint.co.jp/hubfs/resource/topsic/pgb2020/code.pdf

解説VTRがありました。
https://www.youtube.com/watch?v=M_DE9yIkp0Q

1. とりあえずベルが壊れていないと仮定して、剰余でグループ分けする。
2. グループのうち範囲の取り方を網羅。全部の組み合わせを解答としておさえる。
3. ここから壊れているベルをとってしまった組み合わせを除くことを考える。
4. 壊れているベルを含むグループの組み合わせを、いったん全部除く。
5. {1,2,3,4,5}のうち、3がだめだとしたら、{1, 2}と{4, 5}の組み合わせを足す。
これは3C2 + 3C2
6. 全部の壊れているベルグループを加減したら解答。

Q. N=15, D=4とすると

1. 剰余でグループ分けする。
 {1, 5,  9, 13} = 5C2
 {2, 6, 10, 14} = 5C2
 {3, 7, 11, 15} = 5C2
 {4, 8, 12}     = 4C2

2. 全部の組み合わせを解答とする。
4要素の範囲の取り方は5C2 = 10通り。
3要素の範囲の取り方は4C2 = 6通り。

ans = 10*3 + 6*1 = 36

3. M={6, 7, 15}とすると
・まず、6 を含むグループ {2, 6, 10, 14} をなかったことにする。
ans -= 10 // 26

・{2, x, 10, 14}の組み合わせを求める。
{2} と {10, 14}の範囲を加算すればよいので、
ans += 2C2 + 3C2 // 30

・7, 15を含むグループ {3, 7, 11, 15} をなかったことにする。
ans -= 10 // 20

・{3, x, 11, x} の組み合わせを求める。
{3}, {11} なので、
ans += 2C2 + 2C2 // 22

解答は 22

実装。

int main(){
 cincout();
 
 ll N, M, D;
 cin >> N >> M >> D;
 
 map<ll, vector<ll>> MP; // MP[剰余]=壊れたやつマッピング
 rep(i, M){
   ll a;
   cin >> a;
   if (a%D==0) MP[D].push_back(a);
   else MP[a%D].push_back(a);
 }
 // 1,5,9,13 = 5C2通り
 // 1,x,9,13 = 2C2 + 3C2通り
 
 ll ans = 0;
 // いったん全部壊れてないとする
 /*
 {1, 5,  9, 13}
 {2, 6, 10, 14}
 {3, 7, 11, 15}
 {4, 8, 12}
 */
 ll ingre = (N+D-1)/D%MOD; // 4
 ll lucks = D-N%D; // 1
 if (lucks==D) lucks=0; // 割り切れるなら欠損なし
 //k+1C2
 ll add1 = ingre * (ingre+1)%MOD * modinv(2)%MOD;
 //kC2
 ll add2 = ingre * (ingre-1)%MOD * modinv(2)%MOD;
 ll ans1 = add1 * ((D-lucks)%MOD) %MOD ;
 ll ans2 = add2 * lucks % MOD;
 ans = (ans1 + ans2)%MOD;
 ll luckid = oo;
 if (N%D) luckid = N%D+1; // 1~D これ以降が欠損剰余
 for(auto m: MP){
   ll div = m.first;
   if (div < luckid){ // k+1
     (ans = ans - add1 + MOD) %= MOD;
   }
   else{ // k
     (ans = ans - add2 + MOD) %= MOD;
   }
   vector<ll> V = m.second;
   sort(all(V));
   ll tail = (N/D)*D + N%D + D; // 末端+1要素
   V.push_back(tail);
   ll pre = -1;
   ll vsz = V.size();
   rep(v, vsz){
     ll now = ((V[v]-div)/D)%MOD;
     ll bells = (now-pre-1)%MOD;
     ll belladd = bells * (bells+1)%MOD * modinv(2)%MOD;
     (ans += belladd) %= MOD;
     pre = now;
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc223/submissions/26675363