Submission #65022669

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const ll INF = 1e18;
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int N;
ll M;
int A[21][21];
int K,S;
vector<ll> pmod;

inline int key(int x,int y){return (x<<5)|y;}

void dfs_pref(int x,int y,int moves,ll rem,unordered_map<int,vector<ll>>& mp){
    if(moves==K){
        mp[key(x,y)].push_back(rem);
        return;
    }
    ll nrem=(rem*10+A[x][y])%M;
    if(x+1<=N) dfs_pref(x+1,y,moves+1,nrem,mp);
    if(y+1<=N) dfs_pref(x,y+1,moves+1,nrem,mp);
}

void dfs_suf(int x,int y,int steps,int len,ll val,unordered_map<int,vector<ll>>& mp){
    if(steps==S){
        mp[key(x,y)].push_back(val);
        return;
    }
    if(x>1){
        int nx=x-1,ny=y;
        ll nval=(A[nx][ny]*pmod[len]+val)%M;
        dfs_suf(nx,ny,steps+1,len+1,nval,mp);
    }
    if(y>1){
        int nx=x,ny=y-1;
        ll nval=(A[nx][ny]*pmod[len]+val)%M;
        dfs_suf(nx,ny,steps+1,len+1,nval,mp);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(!(cin>>N>>M)) return 0;
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++) cin>>A[i][j];
    if(N==1){
        cout<<A[1][1]%M<<"\n";
        return 0;
    }
    int T=2*N-2;
    K=T/2;
    S=T-K;
    pmod.assign(T+2,1);
    for(int i=1;i<=T+1;i++) pmod[i]=(pmod[i-1]*10)%M;
    unordered_map<int,vector<ll>> pref,suf;
    dfs_pref(1,1,0,0,pref);
    dfs_suf(N,N,0,1,A[N][N]%M,suf);
    for(auto& kv:suf){
        auto& v=kv.second;
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
    }
    ll powsuf=pmod[S+1]%M;
    ll ans=0;
    for(auto& kv:pref){
        int k=kv.first;
        if(!suf.count(k)) continue;
        auto& pre=kv.second;
        auto& sufvec=suf[k];
        for(ll rp:pre){
            ll base=(rp*powsuf)%M;
            ll need=M-1-base;
            auto it=upper_bound(sufvec.begin(),sufvec.end(),need);
            ll cand;
            if(it==sufvec.begin()) cand=(base+sufvec.back())%M;
            else{--it; cand=(base+*it)%M;}
            if(cand>ans) ans=cand;
            if(ans==M-1){cout<<ans<<endl;return 0;}
        }
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result