Submission #65037914

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0; i < (int)(n); ++i)
#define RREP(i, n)    for(int i = (int)(n); i-- > 0;)
#define FOR(i, l, r)  for(int i = (int)(l); i < (int)(r); ++i)
#define RFOR(i, r, l) for(int i = (int)(r); i-- > (int)(l);)
#define ALL(v)        std::begin(v), std::end(v)
using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int, int>;
using namespace std;
constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9 + 7;

template <typename Type>
inline std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
	for(auto &elem : v) is >> elem;
	return is;
}

template <typename Type>
inline std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
	for(auto iter = v.cbegin(); iter != v.cend(); ++iter) os << (iter == v.cbegin() ? "" : " ") << *iter;
	return os;
}

#ifdef DEBUG

#include "debug.hpp"

#else

#define debug(...) static_cast<void>(0)

#endif

// 繰り返し二乗法（mod付き）．O(logK).
constexpr long long mod_pow(long long n, long long k, int mod) {
	assert(k >= 0);
	assert(mod >= 1);
	long long res = 1;
	n %= mod;
	while(k > 0) {
		if(k & 1LL) res = res * n % mod;
		n = n * n % mod;
		k >>= 1;
	}
	return res;
}

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

	vvi a(n,vi(n));
	REP(i,n)REP(j,n) cin>>a[i][j];

	// if(n<=10){
	// 	string s(2*n-1,'0');
	// 	auto calc=[&]()->llong{
	// 		// debug(s);
	// 		llong res=0;
	// 		for(auto c:s) res=(res*10+(c-'0'))%m;
	// 		return res;
	// 	};

	// 	llong ans=0;
	// 	auto dfs=[&](auto self,int y,int x)->void{
	// 		// debug(y,x);
	// 		s[y+x]='0'+a[y][x];
	// 		if(y==n-1 and x==n-1){
	// 			ans=max(ans,calc());
	// 			return;
	// 		}
			
	// 		if(y<n-1) self(self,y+1,x);
	// 		if(x<n-1) self(self,y,x+1);
	// 	};
	// 	dfs(dfs,0,0);

	// 	cout<<ans<<endl;
	// 	return 0;
	// }

	string s(n,'0');
	auto calc=[&]()->llong{
		llong res=0;
		for(auto c:s) res=(res*10+(c-'0'))%m;
		return res;
	};

	vector<vector<llong>> v(n);
	auto dfs=[&](auto self,int y,int x)->void{
		s[y+x]='0'+a[y][x];
		if(y+x==n-1){
			v[y].push_back(calc());
			return;
		}
		if(y<n-1) self(self,y+1,x);
		if(x<n-1) self(self,y,x+1);
	};
	dfs(dfs,0,0);

	vector<vector<llong>> w(n);
	auto dfs2=[&](auto self,int y,int x)->void{
		s[y+x-(n-1)]='0'+a[y][x];
		if(y+x==n-1){
			s[0]='0';
			w[y].push_back(calc());
			return;
		}
		if(y>0) self(self,y-1,x);
		if(x>0) self(self,y,x-1);
	};
	dfs2(dfs2,n-1,n-1);
	for(auto &elem:w) sort(ALL(elem));

	llong ans=0;
	llong ad=mod_pow(10,n-1,m);
	REP(i,n){
		for(auto a:v[i]){
			llong b;
			llong want=m-a*ad%m;
			auto itr=lower_bound(ALL(w[i]),want);
			if(itr==w[i].begin()) b=w[i].back();
			else b=*prev(itr);

			llong tmp=(a*ad%m+b)%m;
			ans=max(ans,tmp);
		}
	}

	cout<<ans<<endl;
}

Submission Info

Judge Result