Handstand 2
StarPatrick
2021-07-20 20:32:23
这是一道我们考试的题（我们的教练太勤快，居然在洛谷茫茫题海中找到了这道藏在角落中的题）。当时我用 $O(n^2)$ 的算法枚举 $(A,B)$ 直接爆掉，所以告诉我们：时间很珍贵。
来，废话不多说，下面步入正题。
**第一种方法**
首先，题目要求的数字对的两个数字，我们只需要知道它们的首尾就行了。
因此，我们可以把 $[1,n]$ 扫一遍，用一个二维桶 $f[i][j]$ 存储首位为 $i$，尾位为 &j& 的数量。
最后，我们就可以计算答案，就是二维桶里所有数字的平方和（因为数对没有位置限制，所以这里是平方）。
时间复杂度 $O(n)$，空间复杂度 $O(1)$
这里代码就不用展示了，因为代码量少，思路清晰简单。
**第二种方法**
这里如果听懂了上一种方法的可以跳过这种方法，不需要掌握，了解即可，因为一般这样的代码长，思维量大，出错率高，不建议在正式比赛采用。
在了解以下内容时，确保你已经看过[@cqbzljt](https://www.luogu.com.cn/blog/LingWang-Blog/solution-at4828)
的第三种方法。
各位读者可能已经知道，她的方法在考虑 **$i$ 的搭档数首位与 $x$ 相等** 时，复杂度比较高且技巧性强（从十位开始加的确有点冒险，数据一大就废了）。
这里，考虑这种情况的时候，答案其实可以通过数学方法算出来，因为首尾两端已确定，我们可以算出中间数字从而求出个数。
时间复杂度 $O(1)$，空间复杂度 $O(1)$
献上我丑陋的代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define int long long
#define max(a,b) a>b?a:b
int n, L, R, ans, f[15][15], len = 1, i;
int quick(int a, int b)//快速幂
{
if (b<0)
{
return 0;
}
if (b==0)
{
return 1;
}
int mid = quick(a, b/2);
if (b%2==0)
{
return mid*mid;
}
else
{
return a*mid*mid;
}
}
signed main()
{
cin>>n;
if(n<10){//特判
cout<<n;
return 0;
}
L = n;
while (L>=10)
{
L/=10;
len++;
}
R = n%10;
i = (n-quick(10, len-1)*L)/10+1;
for (int l=1;l<=9;l++)
{
for (int r=1;r<=9;r++)
{
if (l<L)
{
f[l][r] = quick(10, len-1)/9;
}
else if (l>L)
{
f[l][r] = quick(10, len-2)/9;
}
else
{
if (r>R)//两种情况
{
f[l][r] = i-1+quick(10, len-2)/9;
}
else
{
f[l][r] = i+quick(10, len-2)/9;
}
}
if(l==r)
{
f[l][r]++;
}
}
}
for (int p=1;p<=9;p++)
{
for (int k=1;k<=9;k++)
{
ans+=f[p][k]*f[k][p];
}
}
cout<<ans;
return 0;
}
```