poj1996
2024-10-13 14:30:48
多项式计算,有点像母函数,注意最后要判断最高次项是否为0。
#include <cstdio>
#include <cstring>
using namespace std; #define MAX_NUM 105 int a_num, b_num;
int a[MAX_NUM], b[MAX_NUM];
int c[MAX_NUM * MAX_NUM];
int poly[][MAX_NUM * MAX_NUM];
int poly_num; void input()
{
scanf("%d%d", &a_num, &b_num);
for (int i = ; i <= a_num; i++)
scanf("%d", &a[i]);
for (int i = ; i <= b_num; i++)
scanf("%d", &b[i]);
} void add_c(int poly[], int a)
{
for (int i = ; i <= poly_num; i++)
c[i] += a * poly[i];
} void add_poly(int last[], int next[])
{
memset(next, , sizeof(int) * MAX_NUM * MAX_NUM);
for (int i = ; i <= b_num; i++)
{
for (int j = ; j <= poly_num; j++)
next[i + j] += b[i] * last[j];
}
poly_num += b_num;
} void work()
{
memset(c, , sizeof(c));
for (int i = ; i <= b_num; i++)
{
poly[][i] = b[i];
}
poly_num = b_num;
c[] = a[];
add_c(poly[], a[]);
for (int i = ; i <= a_num; i++)
{
add_poly(poly[(i - ) & ], poly[i & ]);
add_c(poly[i & ], a[i]);
}
while (c[poly_num] == )
poly_num--;
printf("%d", c[]);
for (int i = ; i <= poly_num; i++)
printf(" %d", c[i]);
puts("");
} int main()
{
int case_num;
scanf("%d", &case_num);
for (int i = ; i < case_num; i++)
{
input();
work();
}
}
最新文章
- win7/win8远程桌面 server 2003 卡的问题
- MyBatis mapper文件中的变量引用方式#{}与${}的差别
- Base64 算法原理,以及编码、解码【加密、解密】 介绍
- Leetcode | N-Queens I &; II
- Ubuntu 14.10 下卸载MySQL
- 在RedHat5.4 LINUX 安装mySQL数据库
- IPv6套接字地址结构
- 【转】深入理解Java内存模型(二)——重排序
- Memcached的一些知识
- 两个DIV,左DIV宽度固定,右DIV自动填满剩余空间
- 《算法导论》习题2.3-5 二分搜索 Binary Search
- windows 启动停止 java进程
- 下一代微服务 ~ Service Mesh
- int和integer的区别和使用
- C++命名空间学习笔记
- 手机上输入http://192.168.1.102:8888/FiddlerRoot.cer为什么下载不了证书
- 【设计模式】Javascript设计模式——状态模式(行为型)
- MapReduce程序(一)——wordCount
- 170622、springboot编程之JPA操作数据库
- 20145318《网络对抗》逆向及Bof基础