hdu-1121(差分法--数学问题)

时间:2021-02-28 11:25:30

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1121

参考文章:https://blog.csdn.net/fengzhizi76506/article/details/53729148

思路:有一个n阶序列P(n),从第二项开始每一项减去前一项得到差组成P(n-1)阶序列,直到第0阶,即P(0)。

eg:

i=0  1 2 3 4 5

i=1  1 1 1 1

i=2  0 0 0

i=3  0 0

i=4  0

所以p[i][j]=p[i-1][j+1]-p[i-1][j];

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[][],m,n,i,j,t;
int main(void)
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(i=;i<m;i++) scanf("%d",&a[][i]);
//遍历到0阶的序列
for(i=;i<m;i++)
{
for(j=;j<m-i;j++)
a[i][j]=a[i-][j+]-a[i-][j];
}
//扩展0阶序列
for(i=;i<=n;i++) a[m-][i]=a[m-][];
//依次向上求解,求出后面n个数的值
for(i=m-;i>=;i--)
{
for(j=m-i;j<m+n;j++)
a[i][j]=a[i][j-]+a[i+][j-];
}
for(i=m;i<m+n-;i++) printf("%d ",a[][i]);
printf("%d\n",a[][i]);
}
return ;
}