CF 809 C - Find a car

問題

Problem - C - Codeforces

問題概要

のグリッドがある。上から行目、左から列目のセルをと表す()。各グリッドには、条件に従って数字が書き込まれている。その条件とは、

• に書き込むのは、このマスより左側一直線()と上側一直線()の中に現れていない正の整数の中で最小の値(MEX)。

さて、次のようなクエリがある：

• クエリ : 左上、右下の長方形の中で以下の値についてのみ和を取って、その値をで割った余りを答えよ。

以上のクエリが個与えられるので答えよ。

• 
• 
• 
• 

アイデア

まず、各グリッドには一体どのような数が入るのかという疑問があるが、結論は(i-1)^(j-1) + 1になる。もうこれは経験則というか知識っぽい感じになってしまうが、が依存する位置に注目してみると、これは石山の数が2つのNimと同じだと見なすことができ、またこのMEXがgrundy数と共通する性質を持っているように感じられれば気づけるんだろうか...という気持ちになる。結論ありきだが、帰納的に示すことも出来る。

各グリッドにはどのような値が入るかわかったところで、これらのクエリに答えていく。まず、この長方形の形のクエリは、いつものようにprefixに分解して左上をで固定し、4つの領域に分けて足したり引いたりするやつをすることにする。

1スタートで(i-1)^(j-1) + 1 を考えるのは分かりにくいので、i^j + 1 を考えることにする。更に、i^jと+1を分けて考えると、これは桁dpによって求めることが出来る。

• cnt[bit][small_x?][small_y?][small_k?] : 上位bit個のビットを決定、それぞれx,y,kよりも小さいことが確定しているかという状態で、グリッドの値が以下になっているグリッドの個数
• dp[bit][small_x?][small_y?][small_k?] : 上記の状態で、グリッドの値が以下になっているグリッドの実際の和

この2つを持つことによって、cntを利用してdpが更新でき、最終的に+1の部分でこのcntを利用することができる。このdpは桁数のオーダーでできるので、クエリ上限がなら十分間に合うと考えられる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const ll mod = 1e9+7;

ll cnt[32][2][2][2], dp[32][2][2][2];

ll f(int X, int Y, int K){
    if(X<0 || Y<0 || K<0) return 0;
    memset(cnt,0,sizeof(cnt));
    memset(dp,0,sizeof(dp));

    int xx[32]={},yy[32]={},kk[32]={};
    rep(i,31){
        xx[i] = (X>>(30-i))&1;
        yy[i] = (Y>>(30-i))&1;
        kk[i] = (K>>(30-i))&1;
    }

    cnt[0][0][0][0] = 1;

    // 状態(i,a,b,c)に対して
    rep(i,31)rep(a,2)rep(b,2)rep(c,2){

        // X側はxを、Y側はyを選ぶ
        rep(x,2)rep(y,2){
            int k = x^y;
            if(a==0 && xx[i]<x) continue;
            if(b==0 && yy[i]<y) continue;
            if(c==0 && kk[i]<k) continue;

            int na = a|(x<xx[i]), nb = b|(y<yy[i]), nc = c|(k<kk[i]);
            (cnt[i+1][na][nb][nc] += cnt[i][a][b][c]) %= mod;
            (dp[i+1][na][nb][nc] += dp[i][a][b][c]) %= mod;
            (dp[i+1][na][nb][nc] += (k<<(30-i))*cnt[i][a][b][c]) %= mod;
        }
    }

    ll ret = 0;
    rep(i,2)rep(j,2)rep(k,2){
        ret += dp[31][i][j][k];
        ret += cnt[31][i][j][k];
        ret %= mod;
    }
    return ret;
}

int main(){
    int Q;
    scanf(" %d", &Q);
    while(Q--){
        int x1,y1,x2,y2,k;
        scanf(" %d %d %d %d %d", &x1, &y1, &x2, &y2, &k);
        --x1; --y1; --x2; --y2; --k;

        ll ans = (f(x2,y2,k) - f(x2,y1-1,k) - f(x1-1,y2,k) + f(x1-1,y1-1,k) + 2*mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}