fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int LL;
  4. LL MOD = 998244353;
  5. const int N = 524288;
  6. double PI = acos(-1);
  7. struct comp {
  8. 	double re, im;
  9. 	comp operator*(const comp& a){
  10. 		comp ret;
  11. 		ret.re = re * a.re - im * a.im;
  12. 		ret.im = re * a.im + im * a.re;
  13. 		return ret;
  14. 	}
  15. 	comp operator+(const comp& a){
  16. 		comp ret;
  17. 		ret.re = re + a.re;
  18. 		ret.im = im + a.im;
  19. 		return ret;
  20. 	}
  21. 	comp operator-(const comp& a){
  22. 		comp ret;
  23. 		ret.re = re - a.re;
  24. 		ret.im = im - a.im;
  25. 		return ret;
  26. 	}
  27. };
  28. int getord(int x){
  29. 	int ret = 0;
  30. 	while ((1 << ret) < x) {
  31. 		ret++;
  32. 	}
  33. 	return ret;
  34. }
  35. comp tmp[N];
  36. comp A[N];
  37. comp B[N];
  38. void fft(comp* ar, int n, int mode) {
  39. 	if (n == 1) return;
  40. 	comp base;
  41. 	base.re = cos(2*PI/n);
  42. 	base.im = sin(2*PI/n);
  43. 	if (mode) base.im *= -1;
  44. 	comp cur;
  45. 	cur.re = 1;
  46. 	cur.im = 0;
  47. 	int dnc = n/2;
  48. 	for (int i = 0; i < dnc; i++) {
  49. 		tmp[i] = ar[i*2 + 1];
  50. 	}
  51. 	for (int i = 0; i < dnc; i++) {
  52. 		ar[i] = ar[i*2];
  53. 	}
  54. 	for (int i = 0; i < dnc; i++) {
  55. 		ar[i+dnc] = tmp[i];
  56. 	}
  57. 	fft(ar, dnc, mode);
  58. 	fft(ar + dnc, dnc, mode);
  59. 	for (int i = 0; i < dnc; i++) {
  60. 		comp ta = ar[i];
  61. 		comp tb = ar[i+dnc] * cur;
  62. 		ar[i] = ta + tb;
  63. 		ar[i+dnc] = ta - tb;
  64. 		cur = cur * base;
  65. 	}
  66. }
  67. char str1[200005];
  68. char str2[200005];
  69. int main(){
  70. 	int n, m;
  71. 	scanf("%d%d", &n, &m);
  72. 	scanf("%s", str1);
  73. 	scanf("%s", str2);
  74. 	int L = (1 << getord(n+m+2));
  75. 	for (int i = 0; i < L; i++) {
  76. 		A[i].re = A[i].im = 0;
  77. 		B[i].re = B[i].im = 0;
  78. 	}
  79. 	LL mul = 1;
  80. 	for (int i = 0; i < n; i++) {
  81. 		if (str1[n-i-1] == '1') {
  82. 			A[n-i-1 + 1].re = mul;
  83. 		}
  84. 		mul = (mul*2)%MOD;
  85. 	}
  86. 	for (int i = 0; i < m; i++) {
  87. 		if (str2[i] == '1') {
  88. 			B[m-i-1 + 1].re = 1;
  89. 		}
  90. 	}
  91. 	fft(A, L, 0);
  92. 	fft(B, L, 0);
  93. 	for (int i = 0; i < L; i++) {
  94. 		A[i] = A[i] * B[i];
  95. 	}
  96. 	fft(A, L, 1);
  97. 	LL ans = 0;
  98. 	for (int i = n + 1; i < L; i++) {
  99. 		LL tmp = fmod((A[i].re + 0.5) / L, MOD);
  100. 		ans += tmp;
  101. 		ans %= MOD;
  102. 	}
  103. 	printf("%lld\n", ans);
  104. }
Success #stdin #stdout 0s 40200KB
comments (?)
stdin
copy 
325 325

1111100000111110000011111000001111100000111110000011111000001010111111000001111100000111110000011111000001111100000111110000010101111110000011111000001111100000111110000011111000001111100000101011111100000111110000011111000001111100000111110000011111000001010111111000001111100000111110000011111000001111100000111110000010101

1111100000111110000011111000001111100000111110000011111000001010011111000001111100000111110000011111000001111100000111110000010100111110000011111000001111100000111110000011111000001111100000101001111100000111110000011111000001111100000111110000011111000001010011111000001111100000111110000011111000001111100000111110000010100
stdout
copy 
578292468
https://ideone.com/cdIzUi
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!