原题大意

L先生打算回复来自朋友Z的上一封信，可是他担心信的内容在网络传送过程中出现错误，于是打算采用CRC校验方式保证信息完整性，可是他不知道应该怎么做，请你为他求出应该发送的比特序列。

循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)2^R），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)2^R 除以(模2除法)生成多项式G(x)得到的余数就是校验码。

Input

多组测试例，处理到文件结束。（测试例<5）

每行有两个字符串，用空格隔开，分别为信的内容和生成多项式（长度<=50）。
信的内容为二进制表示。
生成多项式可能用x的多项式,也可能用二进制表示(格式见样例)。

Output

每行输出一个加入CRC后发送的二进制序列，该序列不会长度超过32。

算法分析

模拟。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
string s, t, ss;
int n, r, k;
int read(int i,string t){
    int rr = 0;
    while(isdigit(t[i])){
        rr = rr*10+(t[i] - '0');
        i++;
    }
    return rr;
}
int main(){
    while(cin >> s >> t){
        ss = s;
        int num[100];
        if(t[0] == '0' || t[0] == '1'){
            r = t.length()-1;
            for(int i = 0; i <= r; i++)
                num[i] = t[i] - '0';
        }
        else{            
            r = read(1,t);
            for(int i = 0; i <= r; i++)
                num[i] = 0;
            int size = t.length();
            if(t[size - 1] == '1') num[r] = 1,size-=2;
            if(size >0 && (t[size - 1] == 'x' || t[size - 1] =='X')) num[r-1] = 1,size-=2;
            for(int i = 0; i < size; i++){
                int tt;
                if(isdigit(t[i])) 
                    {
                        tt = read(i,t);
                        num[r-tt] = 1;
                        while(isdigit(t[i])) i++;
                    }
            }

        }
        k = s.length();
        n = k + r;
        for(int i = k; i < n; i++){
            s += '0';
        }
        for(int i = 0; i < n-r; i++){
            if(s[i] != '0'){
                int tmp;
                int cnt = i, cur = 0;
                while(cur <= r){
                    tmp = (s[cnt] - '0') ^ num[cur];
                    s[cnt] = tmp+'0';
                    cur++;
                    cnt++;
                }
//                if(cnt == n) break;
            }
        }
        cout << ss;
        for(int i  = k; i < n; i++){
            cout << s[i];
        }
        cout << endl;
    }
    return 0;
}