本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 17:59:47

[ABC363F] Palindromic Expression

题目考察：记忆化，搜索，数学。
题目简述：
给你一个数 $n$，求一个满足以下条件的字符串 $s$，若没有一个字符串满足条件，输出 $-1$：

• $s$ 由 1，2，3，4，5，6，7，8，9 和 *（即为乘号），注意没有 0。
• $s$ 是一个回文串。
• $s$ 是一个合法的算术表达式且最后计算结果等于 $n$。

数据范围：

• $1\le n\le 10^{12}$

考虑暴力搜索。
对于每一个 $n$，我们考虑找到一对 $n$ 的回文因数 $a,b$（在这里定义回文因数为：若 $a,b$ 为 $n$ 的因数，且 $a,b$ 互为回文，则称 $a,b$ 是一对回文因数），同时 $a,b$ 还不能包含 $0$，那么我们将 $n$ 除以 $a$ 和 $b$，继续往下搜索。
但这样还不行，因为对于 $n=48$，可以经过 2*2*3*2*2 搜索到 $3$，也可以经过 4*3*4 搜索到 $3$，所以我们要用一个 map 来记忆化，也可以用 unordered_map 来省去一个 $\log$。

最终时间复杂度为 $\Theta(\sqrt n\log n)$。
代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define repe(i,x,y) for(i=x;i<=(y);++i) 
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
map<int,string>mp;
inl int rvs(int n){
	reg int x=n,y=0;
	while(x){
		y=(y<<1)+(y<<3)+x%10;
		x\/=10;
	}
	return y;
}
inl bool check0(int n){
	reg int x=n;
	while(x){
		if(!(x%10)) return 0;
		x\/=10;
	}
	return 1;
}
inl bool check(int n){
	return n==rvs(n);
}
inl string getans(int n){
	if(mp.count(n)) return mp[n];
	if(check(n)&&check0(n)) return mp[n]=to_string(n);
	rep(i,2,sqrt(n)){
		reg int rvsi=rvs(i);
		if(n%(i*rvsi)||!check0(i)||!check0(rvsi)) continue;
		reg string s=getans(n\/i\/rvsi);
		if(s=="-1") continue;
		return mp[n]=to_string(i)+"*"+s+"*"+to_string(rvsi);
	}
	return "-1";
}
signed main(){
	fst;
	reg int n;
	cin>>n;
	cout<<getans(n);
	return 0;
}