首页 > 代码库 > 前缀积和后缀积

前缀积和后缀积

2024-07-09 18:07:53   227人阅读

Description:

给出数列A1,A2,...,AN，并设

Bi = (A1 * A2 * A3 ... AN) / Ai mod (109 + 7)

现要求把所有的Bi 算出来

Input:

输入包含多组测试数据。对于每组数据，第1 行，1 个整数N(1 ≤N ≤100,000), 表示数列的长度。第2

行，N 个整数A1,A2,...,AN(1 ≤Ai≤109)，表示给出的数列。输入以一个 0 表示结尾。

Output:

对于每组数据，输出一行，N 个整数用空格分隔，表示算出的B1,B2,...,BN。

Sample Input:

3

1 2 3

0

Sample Output:

6

3

2

 

题意并不难懂

题目给的数据很大，如果一直乘下去，肯定会溢出。所以这里用了一个取余的分配律(a*b)%c=(a%c*b%c)%c

但是这只能得到A1*A2......An，因为取余在除法中没有分配率，所以这里就利用了前缀积和后缀积来解决这个问题。

即:假如n=2,Bi=(A1*A2*A3*A4*A5)%Ai => pre[i]=A1%1000000007 suff[i]=(A3*A4*A5)%1000000007 Bi=pre[i]*suff[i]

代码如下：

 

 1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 using namespace std; 5 long long a[100010],pre[100010],suff[100010]; 6 const int mod=1000000007; 7 int main() 8 { 9     int n,i;10     while(scanf("%d",&n)&&n)11     {12         memset(a,0,sizeof(a));13         for(i=1;i<=n;i++)14             scanf("%lld",&a[i]);15         pre[0]=1;16         for(i=1;i<=n;i++)17             pre[i]=(pre[i-1]*a[i])%mod;18         suff[n+1]=1;19         for(i=n;i>=1;i--)20             suff[i]=(suff[i+1]*a[i])%mod;21         for(i=1;i<=n;i++)22             printf("%lld%c",(pre[i-1]*suff[i+1])%mod,i==n?‘\n‘:‘ ‘);23     }24     return 0;25 }

 


联系
我们