U173215 a+b and a*b without +-*/

 　   a+b and a*b without +-*/

　　给定 $a,b$ ，求 $a+b,a \times b$ 。

　　但是你键盘上的 +-*/ 键坏了。也就是说，你的代码中不能含有 '+', '-', '*', '/' 。

　　对于 $60\%$ 的数据， $1 \leq a,b \leq 10^9$ 。

　　对于所有数据， $1 \leq a,b \leq 10^{10^3}$ 。

　　

　　60pts 的部分分答案不会超过 long long 范围，可以用位运算实现。

　　考虑加法二进制不进位的情况， $a+b = a \oplus b$ 。

　　而对于 $a,b$ 的每一位 $bit$，只有当 $a_{bit} = b_{bit} = 1$ 即 $a_{bit} \land b_{bit} = 1$ 时才会进位。所有要进的位便是 $a \land b$ 。

　　再用左移运算符来模拟进位。所以 $a+b = (a \oplus b)+((a \land b) << 1)$ ，后者的加法运算是可以递归实现的:

inline long long add(long long a,long long b)
{
	return b ?add(a^b,(a&b) << 1):a;
}

　　乘法的实现则可以利用快速乘的思想，即 $a*b = a*(b/2)*2$ ，后者的乘法运算也是可以递归实现的:

inline long long mul(int a,int b) 
{
	long long res=b ?mul(a,b >> 1) << 1:0;
	return b&1 ?add(res,a):res;
}

　　代码总体长度 300B 左右。

 

　　满分做法需要将高精度模板改写，主要考察对字符串的理解运用。

　　高精度的思想即按位运算（这里的位指十进制的位且默认从第 $1$ 位开始）。

　　如果没有想到 60pts 的做法并实现对 $10$ 的除法运算（可以二分结果实现，想法来源于 Loxilante ），需要打表出 0~9 的整数相加与相乘的结果。

　　下面代码中用 $ad,nx,mu,ca$ 数组分别表示相加结果的个位和十位，相乘结果的个位和十位。

　　

　　用 $res$ 表示结果。对于 $res$ 的每一位 $i$ ，用 ${nxt}_i,{car}_i$ 分别表示第 $i$ 位相加相乘进的位，有:

　　${res}_i = (a_i+b_i+{nxt}_{i-1}) \mod 10 , {nxt}_i = \lfloor (a_i+b_i+{nxt}_{i-1})/10 \rfloor$

　　${res}_i = ((\sum_{j=1}^{i} a_{i-j+1} \times b_j)+{car}_{i-1}) \mod 10 , {car}_i = \lfloor ((\sum_{j=1}^{i} a_{i-j+1} \times b_j)+{car}_{i-1})/10 \rfloor$

　　值得一提的是，由于打表数组只能进行个位运算，而乘法运算的进位会有二位数，打表的做法不能直接枚举 $i$ ，需要枚举 $b$ 的每一位 $i$。

　　$res = \sum_{i=1}^{\log_{10} b+1} a \times b_i \times 10^{\log_{10} b+1-i}$ ，时间复杂度还是 $O(\log (ab))$ 。

　　

　　接下来，如何枚举 $i$ 似乎成了难题。60pts 做法的加法实现，定义一个 char 数组用 strlen 函数计数都是可行的。

　　笔者将 $res$ 的类型定义为 std::string ，并用任意非数字字符填满 $res$ ，并用 std::string 的构造函数 find 实现了计数。

　　至此，高精度求和求积实现了:

inline std::string add(std::string a,std::string b)
{
    if((int)a.size()<(int)b.size())
        return add(b,a);
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    std::string res(10050,' ');
    char nxt='0';
    for(int i=0,len=(int)b.size();i<len;i=res.find(' '))
        res[i]=ad[{ad[{a[i],b[i]}],nxt}],nxt=ad[{nx[{a[i],b[i]}],nx[{ad[{a[i],b[i]}],nxt}]}];
    for(int i=(int)b.size(),len=(int)a.size();i<len;i=res.find(' '))
        res[i]=ad[{a[i],nxt}],nxt=nx[{a[i],nxt}];
    if(nxt != '0')
        res[(int)a.size()]=nxt;
    res=res.substr(0,res.find(' '));
    reverse(res.begin(),res.end());
    return res;
}

　　

inline std::string mul(std::string a,std::string b)
{
    reverse(b.begin(),b.end());
    std::string res;
    char cnt[10050]={};
    for(int i=0,len=(int)a.size();i<len;cnt[i]='0',i=strlen(cnt))
    {
        std::string tmp(10050,' ');
        char car='0';
        for(char c:b)
        {
            int j=tmp.find(' ');
            tmp[j]=ad[{mu[{a[i],c}],car}],car=ad[{ca[{a[i],c}],nx[{mu[{a[i],c}],car}]}];
        }
        if(car != '0')
            tmp[(int)b.size()]=car;
        tmp=tmp.substr(0,tmp.find(' '));
        reverse(tmp.begin(),tmp.end());
        std::string nres(10050,' ');
        for(auto c:res)
            nres[nres.find(' ')]=c;
        nres[(int)res.size()]='0';
        nres=nres.substr(0,nres.find(' '));
        res=add(tmp,nres);
    }
    return res;
}

　　如果没有想到用 60pts 的做法来实现个位运算，码量还是比较大的（算上打表数组 8KB 左右），但也能加深对 std::string 的理解。

　　当然，题目更希望加深选手们对位运算的理解。

 

　　接下来是 fun fact :

　　笔者是不会判断代码中是否有不允许的字符的，所以写了个 Special Judge 来骗你（这个 spj 还是有点用的，可以显示你加法还是乘法写错了）。

　　希望选手们自觉！不要拿个模板或者其他自带高精的语言来水题！

　　你坏的键盘也不是普通的键盘，至少 '+' 和 '=' ，'/' 和 '?' 是分开的。（雾）