ABC402個人的備忘録[A-D,F] #C++ – Qiita

#include 
using namespace std;
using ll = long long;

//高速で累乗のmodを求める関数
ll fuc(ll n,ll mod){
    ll now = 10,ans = 1;

    while(n != 0){
        if(n%2 == 1) ans *= now;
        ans %= mod;
        now *= now;
        now %= mod;

        n >>= 1;
    }

    return ans;
}

int main(){
    ll n,m;
    cin >> n >> m;

    vectorvectorll>>num (n,vectorll>(n));

    ll pw = (n-1)*2;
    for(int i=0;in;i++){
        for(int j=0;jn;j++){
            ll x;
            cin >> x;

            //あらかじめデータを足し算にできるよう加工
            num[i][j] = x*fuc(pw-i-j,m);
            num[i][j] %= m;
        }
    }

    vectorvectorll>>upd (n,vectorll>(0)),dwd (n,vectorll>(0));
    queuepairpairint,int>,ll>>que;
    que.push({{0,0},num[0][0]});

    //まずは上側からBFS
    while(!que.empty()){
        auto [aaa,cst] = que.front();
        auto [x,y] = aaa;
        que.pop();

        //中央に来たら打ち切り
        if(x+y == n-1){
            upd[x].push_back(cst);
            continue;
        }

        //右もしくは下に移動(mod計算を忘れない)
        ll sum = cst + num[x+1][y];
        sum %= m;
        que.push({{x+1,y},sum});

        sum = cst + num[x][y+1];
        sum %= m;
        que.push({{x,y+1},sum});
    }

    que.push({{n-1,n-1},num[n-1][n-1]});
    //今度は下側からBFS
    while(!que.empty()){
        auto[aaa,cst] = que.front();
        auto[x,y] = aaa;
        que.pop();

        //中央に来たら打ち切り
        if(x+y == n-1){
            //二回中央の値を足してるので調整
            cst = m + cst - num[x][y]; 
            dwd[x].push_back(cst%m);
            continue;
        }

        //左もしくは上に移動
        ll sum = cst + num[x-1][y];
        sum %= m;
        que.push({{x-1,y},sum});
        
        sum = cst + num[x][y-1];
        sum %= m;
        que.push({{x,y-1},sum});
    }

    ll ans = 0;

    for(int i=0;in;i++){
        sort(dwd[i].begin(),dwd[i].end());

        //すべてのXについて最も大きな値になれるYを二分探査
        for(auto x:upd[i]){
            ll mx = m - x - 1;
            int p  = upper_bound(dwd[i].begin(),dwd[i].end(),mx) - dwd[i].begin();

            ll a;

            if(p != 0){
                a = x + dwd[i][p-1];                
            }else{
                a = dwd[i].back();
                a = (a+x)%m;
            }
            //答えを更新
            ans = max(ans,a);
        }
        
    }

    cout  ans  endl;    
}