CodeForces Round #515 Div.3 E. Binary Numbers AND Sum
http://codeforces.com/contest/1066/problem/E
You are given two huge binary integer numbers b), and repeat the process again, otherwise stop the process.
The value 998244353.
Note that you should add the value 1000.
Input
The first line of the input contains two integers b correspondingly.
The second line of the input contains one huge integer 1.
The third line of the input contains one huge integer 1.
Output
Print the answer to this problem in decimal notation modulo 998244353.
Examples
input
Copy
4 4
1010
1101
output
Copy
12
input
Copy
4 5
1001
10101
output
Copy
11
代码：
#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, 0, 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("1
");
else if(M == 1 && A[N - 1] == '0')
printf("0
");
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("%I64d
", ans % 998244353);
}
return 0;
}