题解：P14565 翻转

i_love_xqh · 2025-11-21 16:44:51 · 题解

不妨设 \overline{b_1\cdots b_ka_k\cdots a_1}x=\overline{a_1\cdots a_kb_k\cdots b_1}。比较显然的是 1\le x<k。

考虑从两边往中间填，先枚举倍数。如果填了 a_1\sim a_i 是容易算出 b_1\sim b_i 并知道 a_i 会向 a_{i+1} 进多少位，以及 b_{i+1} 需要向 b_i 进多少位。于是设 f_{i,j,k} 表示从低往高考虑到第 i 位，第 i 位向 i+1 位进了 j 位，第 n-i 位需要向第 n-i+1 位进 k 位。

如果直接枚举状态和第 i+1 位填什么时间复杂度是 O(k^3\log_k n) 的，再加上枚举倍数就是 k^4 了。事实上发现只需要枚举第 i+1 位填 a 和第 i 位向第 i+1 位进了 j_1 位，然后就能求出 b 和第 i+1 位会向第 i+2 位进 k_1 位，进而知道第 n-i 向第 n-i+1 位的进位 j_2 和第 n-i 位需要第 n-i-1 进 k_2 位。所以便由 f_{i,j_1,j_2}\to f_{i+1,k_1,k_2}。

然后需要分讨长度为奇偶的情况，以及当长度恰好为 \log_k n 时还需记录 0,1,2 表示高位 <、高位 = 低位 \le、高位 = 低位 >，类似数位 dp 的 limit。合并差不多。

一个卡常小技巧是对于一个进制，有一些倍数一定不存在，可以打表出来不枚举即可。当然也可以写记忆化搜索。

附一份未经卡常的代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int p=998244353;
char s[N];
int pos[N];
int f[N>>1][16][16][2][2],g[N>>1][16][16];
void chmod(int &x,int y){x+=y;if(x>=p)x-=p;}
int main(){
    int k;scanf("%d",&k);
    scanf("%s",s+1);int n=strlen(s+1);
    for(int i=1;i<=n;i++)pos[i]=(s[i]>='0'&&s[i]<='9'?s[i]-'0':s[i]-'A'+10);
    int l=(n-1)/2,ans=0;//<n
    for(int x=1;x<k;x++){
        for(int i=0;i<=l;i++)for(int j1=0;j1<k;j1++)for(int j2=0;j2<k;j2++)g[i][j1][j2]=0;
        g[0][0][0]=1;
        for(int i=1;i<=l;i++){
            for(int a=0;a<k;a++){
                for(int j1=0;j1<k;j1++){
                    int b=(a*x+j1)%k,k1=(a*x+j1)/k,k2;
                    if(i==1&&!b)continue;
                    int c=b*x%k,j2=b*x/k;
                    if(c<=a)k2=a-c;else j2++,k2=k-c+a;
                    int &v=g[i-1][j1][j2];
                    if(!v)continue;
                    chmod(g[i][k1][k2],v);
                }
            }
        }
        for(int i=1;i<=l;i++){
            for(int j=0;j<k;j++){
                if(!g[i][j][j])continue;
                chmod(ans,g[i][j][j]);
            }
        }
        for(int i=0;i<=(n&1?l-1:l);i++){
            for(int j1=0;j1<k;j1++){
                for(int a=(i==0);a<k;a++){
                    int b=(a*x+j1)%k;if(b!=a)continue;
                    int j2=(a*x+j1)/k;if(!g[i][j1][j2])continue;
                    chmod(ans,g[i][j1][j2]);
                }
            }
        }
    }
    l=n/2;//=n
    for(int x=1;x<k;x++){
        for(int i=0;i<=l;i++)for(int j1=0;j1<k;j1++)for(int j2=0;j2<k;j2++)for(int l1=0;l1<2;l1++)for(int l2=0;l2<2;l2++)f[i][j1][j2][l1][l2]=0;
        f[0][0][0][1][0]=1;
        for(int i=1;i<=l;i++){
            for(int l1=0;l1<2;l1++){
                for(int l2=0;l2<2;l2++){
                    for(int a=0;a<k;a++){
                        for(int j1=0;j1<k;j1++){
                            int b=(a*x+j1)%k,k1=(a*x+j1)/k,k2;
                            if(i==1&&!b)continue;
                            if(l1&&b>pos[i])continue;
                            int c=b*x%k,j2=b*x/k;
                            if(c<=a)k2=a-c;else j2++,k2=k-c+a;
                            int &v=f[i-1][j1][j2][l1][l2];
                            if(!v)continue;
                            int L1=l1&&b==pos[i],L2=a==pos[n-i+1]?l2:(a>pos[n-i+1]);
                            chmod(f[i][k1][k2][L1][L2],v);
                        }
                    }
                }
            }
        }
        if(n&1){
            for(int j1=0;j1<k;j1++){
                for(int a=(n==1);a<k;a++){
                    int b=(a*x+j1)%k;if(b!=a)continue;
                    int j2=(a*x+j1)/k;
                    for(int l1=0;l1<2;l1++){
                        for(int l2=0;l2<2;l2++){
                            int &v=f[l][j1][j2][l1][l2];
                            if(!v)continue;
                            if(l1&&(a>pos[l+1]||(a==pos[l+1]&&l2)))continue;
                            chmod(ans,v);
                        }
                    }
                }
            }       
        }
        else{
            for(int j=0;j<k;j++){
                for(int l1=0;l1<2;l1++){
                    for(int l2=0;l2<2;l2++){
                        int &v=f[l][j][j][l1][l2];
                        if(!v)continue;
                        if(l1&&l2)continue;
                        chmod(ans,v);           
                    }
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}