题解 | A*BBBB

A*BBBB：原题链接

题意：

     给你两个值a和b，b的每一位都相同，求它们相乘后的结果。

注意：a和b的长度有1e6。

做题思路：

     很显然本题需要用到高精度，但普通高精度并不能解决本题，所以要针对本题做出优化。

     首先根据题意我们可以知道b的每一个值都是相同的，我们用个样例，看看可以得出什么。

样例假设：a=1234,b=111

     我们列出计算公式后，可以发现每一行的值都是相同的，在计算相加时，当前位置的值是该点原先的值加上它右侧的值，如，个位上为4，十位上为3+4=7，百位上为2+7=9，出于累加状态。

    1 2 3 4
  1 2 3 4
1 2 3 4
1 3 6 9 7 4

     很显然位置上的值不会一直出于累加状态，如千位上的值为1+2+3，将个位上的值4去除了，每个点上的值是怎么累加的呢，我们建个表直观感受一下。

     有没有感觉到什么，是不是很像滑动窗口，当超出k时，就将超出k的部分弹出，而这个k值很明显就是b的长度，由此可以得到一条规则

//now为计数，当在超出b的长度后，此时i-lenb上的值已经超出，所以减去 
if (i>=lenb)now-=a[i-lenb]-'0';

     但这显然完成不了代码，我们继续模拟。

     此时我们发现值一直在减少，原因很简单，它没东西可以加了嘛，当第一行的值加完时，now也同样不会继续累加。

    | 1 2 3 4
  1 | 2 3 4
1 2 | 3 4
1 3 | 6 9 7 4

     所以得出以下代码

//当在超出a的长度前，下一位值会处于累加状态 
if (i<lena)now+=a[i]-'0';

     接下来接可以使用经典的高精度解决问题了，可能有人问这只是当b相同值等于1的情况，要是不想同怎么办，那么ad+bd+cd是不是等于(a+b+c)*d，所以只要在高精度计算余数的部分乘以b[0]就可以了，并不会对题目造成影响。以下是AC代码。

#include <bits/stdc++.h>
using namespace std; 

const int N=1e7+10;
int t;
string a,b;

int main(){
	cin >>t;
	while(t--)
	{
		cin >>a>>b;
		//怎么来的让他怎么回去吧
		//数组存不下本题答案 
		string s="";
		//res记录每次按位计算时的值 
		int res=0;
		//因为b每一位都相同，所以直接拿出用来计算 
		int op=b[0]-'0';
		//拿出a,b的长度，便于计算 
		int lena=a.size();
		int lenb=b.size();
		//now为当前个位的值 
		int now=0;
		//因为是乘法计算，所以最终答案的长度会是两者相加减一 
		int maxn=lena+lenb;
		//因为从个位开始算起，所以将字符串倒叙 
		reverse(begin(a),end(a));
		for (int i=0;i<maxn;i++)
		{
			//当在超出a的长度前，下一位值会处于累加状态 
			if (i<lena)now+=a[i]-'0';
			//当在超出b的长度后，此时i-lenb上的值已经超出，所以减去 
			if (i>=lenb)now-=a[i-lenb]-'0';
			//计算该位置上的值 
			res+=now*op;
			//将他的余数放入s尾 
			s.push_back(res%10+'0');
			//并将余数除10，确保余数是个位数 
			res/=10;
		}
		//删除前导0 
		while(s.size()>1 && s.back()=='0')s.pop_back();
		//将s从逆序变正序 
		reverse(begin(s),end(s));
		cout <<s<<"\n";
	}
    return 0;
}