Atcoder ABC 402

compaq · 2025-04-20 11:36:09 · 题解

#include<bits/stdc++.h>
using namespace std;
int n,m,a[25][25],pw[50];
vector<int>g1[25],g2[25];
int main(){
    scanf("%d%d",&n,&m);
    //1.预处理a 乘上权值
    pw[0]=1;
    for(int i=1;i<=n*2-2;i++)
        pw[i]=(pw[i-1]*10ll)%m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            a[i][j]=(1ll*a[i][j]*pw[n*2-i-j])%m;
        }
    //2.从(1,1)出发走一半路程到(x,n-x+1) 即n-1步 用二进制枚举过程 1向下 0向右
    for(int i=0;i<(1<<(n-1));i++){
        int x=1,y=1,res=a[1][1];
        for(int j=0;j<n-1&&x<=n&&y<=n;j++){
            if((i>>j)&1) x++;
            else y++;
            res=(res+a[x][y])%m;//先走后加
        }
        if(x<=n&y<=n) g1[x].push_back(res);//将有效答案存入g1
    }
    //3.从(n,n)出发走一半路程到(x,n-x+1) 即n-1步 用二进制枚举过程 1向上 0向左
    for(int i=0;i<(1<<(n-1));i++){
        int x=n,y=n,res=0;
        for(int j=0;j<n-1&&x>=1&&y>=1;j++){
            res=(res+a[x][y])%m;//避免重复计算(x,n-x+1)的点 先加后走
            if((i>>j)&1) x--;
            else y--;
        }
        if(x>=1&&y>=1) g2[x].push_back(res);//存入g2
    }
    //4.贪心匹配两组答案
    int ans=0;
    for(int i=1;i<=n;i++){//考虑每个相交的点
        sort(g1[i].begin(),g1[i].end());//将所有答案排序
        sort(g2[i].begin(),g2[i].end());
        for(int x=g1[i].size()-1,y=0;x>=0;x--){//固定g1 找到最大的g2
            while(y<g2[i].size()&&g1[i][x]+g2[i][y]<m) y++;//不取模下的最大值
            if(y) ans=max(ans,g1[i][x]+g2[i][y-1]);//判断数组越界
            ans=max(ans,(g1[i][x]+g2[i].back())%m);//取模一定取最大值
        }
    }
    printf("%d",ans);
    return 0;
}//第三