ABC-363-D- Palindromic Number · znzryb
## AC代码
回文数生成算法
**前面搞半天没过，原来是pow的问题，pow只会返回int，导致int溢出了。**
自己手搓了一个lpow就过了。
主要原理是经过观察
那么i位回文数就有9*10**((i-1)/2)个（/2为向下取整）
然后我们要确定回文数母体，
[](https://atcoder.jp/contests/abc363/submissions/59551360)
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;
ll lpow(int a,int b) {
return {b==0 ? 1: lpow(a,b-1)*a};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
if(n==1) {
cout<<0<<endl;
return 0;
}
ll cnt=0;
n-=1;
bool isOdd=true;
for(int i=1;i<=n;++i) {
cnt+=9*lpow(10,(i-1)/2);
if(cnt>=n) {
cnt-=9*lpow(10,(i-1)/2);
ll ten;ten= lpow(10,(i-1)/2);
ten-=1;
ll remain=ten+n-cnt;
// 把remain存入ans数组
while (remain) {
ans.push_back(remain%10); // 900 存入后是 0 0 9
remain/=10;
}
if(i%2==0)
isOdd=false;
break;
}
}
if(isOdd) {
for(int i=ans.size()-1;i>=0;--i)
cout<<ans[i];
for(int i=1;i<=ans.size()-1;++i)
cout<<ans[i];
cout<<endl;
}else {
for(int i=ans.size()-1;i>=0;--i)
cout<<ans[i];
for(int i=0;i<=ans.size()-1;++i)
cout<<ans[i];
cout<<endl;
}
}
// AC https://atcoder.jp/contests/abc363/submissions/59551360
```
## 心路历程（WA，TLE，MLE……）
[](https://atcoder.jp/contests/abc363/submissions/59549576)
虽然样例吧都过不了，但我百思不解为何WA，对拍程序生成的都没WA呀。
**搞半天原来是pow的问题，pow只会返回int，导致int溢出了。**
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
if(n==1) {
cout<<0<<endl;
return 0;
}
ll cnt=0;
n-=1;
bool isOdd=true;
for(int i=1;i<=n;++i) {
cnt+=9*pow(10,(i-1)/2);
if(cnt>=n) {
cnt-=9*pow(10,(i-1)/2);
ll ten;ten= pow(10,(i-1)/2);
ten-=1;
ll remain=ten+n-cnt;
// 把remain存入ans数组
while (remain) {
ans.push_back(remain%10); // 900 存入后是 0 0 9
remain/=10;
}
if(i%2==0)
isOdd=false;
break;
}
}
if(isOdd) {
for(int i=ans.size()-1;i>=0;--i)
cout<<ans[i];
for(int i=1;i<=ans.size()-1;++i)
cout<<ans[i];
cout<<endl;
}else {
for(int i=ans.size()-1;i>=0;--i)
cout<<ans[i];
for(int i=0;i<=ans.size()-1;++i)
cout<<ans[i];
cout<<endl;
}
}
```