题解：P14565 翻转

不妨设

\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。合并差不多。

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

附一份未经卡常的代码。

CPP

#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;
}

文章操作

相关推荐

评论

题解：P14565 翻转