CodeForces E. Binary Numbers AND Sum

发布时间：2020-12-14 04:18:12 所属栏目：大数据来源：网络整理

导读：http://codeforces.com/contest/1066/problem/E ? You are given two huge binary integer numbers? a a?and? b b?of lengths? n n?and? m m?respectively. You will repeat the following process: if? b 0 b0,then add to the answer the value? a ? ? b a

http://codeforces.com/contest/1066/problem/E

You are given two huge binary integer numbers? $a$

The value? $a & b$

Note that you should add the value? $a & b$

Input

The first line of the input contains two integers? $n$

The second line of the input contains one huge integer? $a$

The third line of the input contains one huge integer? $b$

Output

Print the answer to this problem in decimal notation modulo? $998244353$

Examples

input

Copy

4 4
1010
1101

output

Copy

input

Copy

4 5
1001
10101

output

Copy

代码：

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

typedef long long ll;
int N,M;
char A[200010],B[200010];
ll sum[200010];

ll Pow(ll x,ll n,ll mod) {
    ll res = 1;
    while(n > 0) {
        if(n % 2 == 1) {
            res = res * x;
            res = res % mod;
        }
        x = x * x;
        x = x % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d",&N,&M);
    scanf("%s%s",A,B);
    memset(sum,sizeof(sum));
    for(int i = N - 1; i >= 0; i --) {
        sum[N - 1 - i] =(A[i] - ‘0‘) * Pow(2,N - 1 - i,998244353) + sum[N - i - 2];
        sum[N - 1 - i] %= 998244353;
    }

    if(M == 1 && A[N - 1] == ‘1‘)
        printf("1n");
    else if(M == 1 && A[N - 1] == ‘0‘)
        printf("0n");
    else {
        ll ans = 0;
        for(int i = 0; i <= N / 2 - 1; i ++)
            swap(A[i],A[N - 1 - i]);
        for(int i = 0; i <= M / 2 - 1; i ++)
            swap(B[i],B[M - 1 - i]);

        for(int i = 0; i < M; i ++) {
            if(B[i] == ‘1‘) {
                if(i >= N)
                    sum[i] = sum[N - 1];
                ans += sum[i];
                ans %= 998244353;
            }
        }
        printf("%I64dn",ans % 998244353);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!