D

D:A * BBBB

题目分析：

算法一 O(a.size() * b.size())：(超时)

我们遍历b.size()次，每次对a[i+j]位置加上a[j]即可

#include <cstring>
#include <iostream>
using namespace std;

const int N = 2e6 + 10;
string a;
int s[N];
char b[N];
int c[N]; // 存数

void solve()
{
    cin >> a;
    cin >> b;
    int x = b[0] - '0';
    int n = strlen(b);
    int num = 0;
    memset(c, 0, sizeof c);
    memset(s, 0, sizeof s);
    for (int i = a.size() - 1; i >= 0; i--)
    {
        c[num] += (a[i] - '0') * x;
        if (c[num] > 9) c[num + 1] += c[num] / 10, c[num] %= 10;

        num++;
    }

    int len = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < num; j++)
        {
            s[i + j] += c[j];
            len = max(len, i + j);
        }
    }

    for (int i = 0; i <= len; i++)
    {

        if (s[i] > 9) s[i + 1] += s[i] / 10, s[i] %= 10, len = max(len, i);
    }
    for (int i = len; i >= 0; i--)
    {

        cout << s[i];
    }
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

思路二 （来源：忧郁土豆片 时间复杂度（O（a.size()+b.size()））

(非原创)（侵删）

为了方便理解，我们设 a = 114514,b = 2222;

有以下列式

      1 1 4 5 1 4 * 2
    1 1 4 5 1 4 * 2
  1 1 4 5 1 4 *2
1 1 4 5 1 4 *2

设 i 位第i位答案 由上图我们可以观察到 所有的数字都乘了b[0]，所以b【0】可以在处理完之后乘 我们从后往前看 （i是从后往前定义的）

ans[1] = a[1] x 2 ;
ans[2] = a[1]+a[2] x 2;
ans[3] = a[1]+a[2]+a[3]x 2;
ans[4] = a[1]+a[2]+a[3]+a[4] x 2;
ans[5] = a[2]+a[3]+a[4]+a[5] x 2;
ans[6] = a[3]+a[4]+a[5]+a[6] x 2;
ans[7] = a[4]+a[5]+a[6] x 2;
ans[8] = a[5]+a[6] x 2;
ans[9] = a[5] x 2;

从上面我们不难发现 决定ans[i]的值的个数与a,b的长度有关，当[i]<a.size()时不断加入a[i]，当i>a.size()时停止,当i>b.size时ans[i]相对ans[i-1]又减去了a[i-b.size()]; 所以我们可以用前缀和去优化该过程 int cnt = 0; 用cnt表示ans[i]; 由上边推导可得

当i<a.size()时cnt+=a[i]; 当i>b.size()cnt-=a[i-b.size()]; 因为是乘法，所以会出现进位 然后我们利用cur1去处理一下进位问题

#include <iostream>
#include <cstring>
#include<algorithm>
using namespace std;

void solve()
{

    string a, b;
    string ans;
    cin >> a >> b;
    reverse(begin(a), end(a));
    int cur = 0, temp = 0;

    for (int i = 0; i < a.size() + b.size(); i++)
    {

        //cur对应推导过程中的ans[i]
        //temp 用来解决进位问题
        if (i < a.size()) cur += a[i] - '0';
        if (i >= b.size()) cur -= a[i - b.size()] - '0';
        temp += cur * (b[0] - '0');
        ans.push_back(temp % 10 + '0');
        temp /= 10;
    }
    while (ans.size() > 1 && ans.back() == '0')
        ans.pop_back();
    reverse(begin(ans), end(ans));
    cout << ans << "\n";
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}