专业门户网站开发,浙江省湖州艺术与设计学校官网,wordpress做复杂网站,网站建设报价请示题目描述#xff1a; 小花有一个数组A#xff0c;小树有一个数组B。小花和小树的关系很好#xff0c;他们希望合并手中的数组#xff0c;得到新的集合C{ab|a∈A, b∈B}。
输入格式#xff1a;第一行输入两个整数N,M#xff0c;分别表示数组A,B的长度。第二行包含N个整数…题目描述 小花有一个数组A小树有一个数组B。小花和小树的关系很好他们希望合并手中的数组得到新的集合C{ab|a∈A, b∈B}。
输入格式第一行输入两个整数N,M分别表示数组A,B的长度。第二行包含N个整数表示数组A。第三行包含M个整数表示数组B。 (0 ≤ N,M ≤ 2 *10^5, 0 ≤ A[i],B[i] ≤ 2 * 10^6)
输出格式输出一个整数表示C的元素个数。
输入样例
10 10
12 14 0 2 2 15 26 17 8 44
1 4 6 10 22 13 19 50 39 0
输出样例
56
注意本题时间限制较严格由于暴力解法时间复杂度为O(n^2)可能无法满足本题要求因此请尽可能优化你的算法 6000ms512MB。
分析我们首先想到的算法就是暴力解法用双重循环实现。源程序如下 #include stdio.h
#include stdlib.h
#include string.hint main(void)
{int n, m;scanf(%d %d, n, m);int* arrl(int*)malloc(sizeof(int) * n);int* arr2(int*)malloc(sizeof(int) * n);if (arrlNULL || arr2 NULL) return 1; for (int i 0; i n; i) {scanf(%d,arrl[i]);}for(int i 0; i m; i) {scanf(%d,arr2[i]);}char* check (char*)malloc(sizeof(char) * 4000001);if (check NULL) return 1;memset (check, 0, sizeof(char) * 4000001);int count 0;for (int i 0; i n; i) {for (int j 0; j m; j) {check[arrl[i] arr2[j]]1; }}for(int i0; i 4000001; i){count check[i];}printf(%d\n,count);return 0;
}
暴力算法虽然简单但数据量大时运行时间会超时因为算法的时间复杂度为O(n^2)无法满足题目要求。因此必须找到一种解决方案。因此有网友提出一种方案使用傅里叶变换实现。
设A数组[0, 1, 3, 5, 6]中的元素可看成多项式1xx^3x^5x^6)的系数B数组中[2,3,4]中的元素可看成多项式(x^2x^3x^4)的系数。计算这两个多项式的乘法1xx^3x^5x^6)*(x^2x^3x^4)然后看结果中哪些项前面有系数统计有系数项的个数即为所求答案。
使用快速傅里叶变换进行多项式乘法运算其时间复杂度为Onlogn)应能满足题目要求。源程序如下。 #include stdio.h
#define LLONG long long
#define MAXN (123)
#define mod 998244353 //质数,在编程中常被用来做模数
int id[MAXN];
int a[ MAXN],b[ MAXN];
int quickpow(int x, int b)
{LLONG ans1,tx;while(b){if(b1) ansans*t%mod;tt*t%mod;b1;}return ans;
}
int init(int len)
{int lim1;while(limlen) {lim1;}for(int i1; ilim; i){id[i] (id[i1]1)(i1)*(lim1);}return lim;
}
void NTT(int a[],int lim, int opt)
{for(int i1; ilim; i){if(iid[i]) {int step a[i];a[i] a[id[i]];a[id[i]] step;}}for(int len2; lenlim; len1) {int klen1;int wnquickpow(3,(mod-1)/len);for(int i0; ilim; ilen){LLONG g1;for(int j0; jk; j,gg*wn%mod){int tempa[ijk]*g%mod;a[ijk](mod-tempa[ij])%mod;a[ij](a[ij]temp)%mod;}}}if(opt-1) { for (int i 0; i lim; i){int temp a[i1];a[i1] a[lim - i];a[lim - i] temp;}LLONG invquickpow(lim,mod-2);for(int i0; ilim; i) {a[i]a[i]*inv%mod;}}return;
}
int main()
{int n,m,lim0;int x,i;scanf(%d%d,n,m);for(i1; in; i) {scanf(%d,x);a[x]1;if(xlim)limx;}for(i1; im; i) {scanf(%d,x);b[x]1;if(xlim)limx;}lim init(lim1);NTT(a,lim,1);NTT(b,lim,1);LLONG step;for(i0; ilim; i){step a[i];a[i]step*b[i]%mod;}NTT(a,lim,-1); for(i0,n0; ilim; i) {if(a[i]) n;}printf(%d,n);return 0;
}
参考文献
[1]https://tieba.baidu.com/p/8844914020
[2]百度网盘资源下载网址
https://pan.baidu.com/s/17ZXphwqySNIsIgcGtYMjvg?pwdlhwc
[3]李红卫李秉璋. C程序设计与训练第四版[M]大连大连理工大学出版社2023.
