Submission #65038890

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll modexp(ll base, int exp, int mod) {
    ll result = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    vector<vector<int>> a(N, vector<int>(N));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> a[i][j];
        }
    }
    
    int moves = N - 1;
    vector<map<int,int>> mp1(N);
    for (int mask = 0; mask < (1 << moves); mask++){
        int r = 0, c = 0;
        int F = a[0][0] % M;
        for (int j = 0; j < moves; j++){
            if(mask & (1 << j))
                r++;     
            else
                c++;   
            F = (int)(((ll)F * 10 + a[r][c]) % M);
        }
        mp1[r][F]++;
    }
    vector<map<int,int>> mp2(N);
    for (int r = 0; r < N; r++){
        for (int mask = 0; mask < (1 << moves); mask++){
            if(__builtin_popcount(mask) != (moves - r))
                continue;
            int cr = r, cc = (N - 1 - r);
            int T = 0;
            for (int j = 0; j < moves; j++){
                if(mask & (1 << j))
                    cr++;
                else
                    cc++;
                T = (int)(((ll)T * 10 + a[cr][cc]) % M);
            }
            mp2[r][T]++;
        }
    }

    int factor = (int)modexp(10, moves, M);
    int ans = 0;
    for (int r = 0; r < N; r++){
        for (auto &p : mp1[r]){
            int F = p.first;
            int X = (int)(((ll)F * factor) % M);
            
            if(mp2[r].empty()) continue;
            
            int currentCandidate = 0;
            
            int threshold = M - X;
            auto it = mp2[r].lower_bound(threshold);
            if(it != mp2[r].begin()){
                int T_candidate = prev(it)->first;            
                int candidate1 = X + T_candidate;
                currentCandidate = candidate1;
            }
            
            int T_max = mp2[r].rbegin()->first;
            int candidate2 = (X + T_max) % M;
            currentCandidate = max(currentCandidate, candidate2);
            
            ans = max(ans, currentCandidate);
        }
    }
    
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result