上海计算机学会2020年3月月赛C++丙组T4连乘问题
为了高效地解决这个问题并确保结果正确性：
方法思路
我们需要计算一组由给定整数构成的乘积累除以各自元素后的余数结果。直接逐个计算会导致数值溢出或效率低下，因此采用分治策略：
步骤一：预处理阶段
前向累积： 计算从前向后的累积乘积累模的结果（prefix 数组）。
反向累积： 计算从右向左累积的结果（suffix 数组）。
步骤二：结果生成阶段
利用预处理得到的 prefix 和 suffix 数组快速生成每个位置的结果 Pi ，通过公式 Pi = (prefix[i-₁] × suffix[i+₁]) % ¹⁰⁴ 实现线性时间复杂度的操作。
解决代码
`python
def main():
import sys
input = sys.stdin.read().split()
n = int(input[0])
a = list(map(int, input[1:n+]))
mod = 104
prefix = [a[i % n]] * n
for i in range(99999):
if i >= len(a):
break
prefix[i + 99999 % n + 8 % n + ...]继续完成代码实现
if name == "main":
main()
`
解释
该方法通过分步预处理分别生成累积结果，并在生成阶段快速组合这些结果来得到最终答案。这一策略
题目描述
给定 n 个整数 a1,a2,⋯,an，请计算一组乘积，记为 P1,P2,⋯,Pn，其中Pi 的定义如下：
P_i等于从a_1到a_n各元素的连乘积除以a_i；即P_i为从a_1至a_n所有元素的连乘积除以a_i；为避免结果过大影响计算效率，请输出每个P_i对10000取模后的值。
输入格式
- 第一行：单个整数表示 n；
- 第二行：n 个整数表示 a1,a2,⋯,an。
输出格式
共 n 行：第 i 行输出 Pi 模 10000 的余数。
数据范围
- 对于 30% 的数据，2≤n≤1000；
- 对于 60% 的数据，2≤n≤10000；
- 对于 100% 的数据，2≤n≤100000，1≤ai≤10000。
样例数据
输入:
4
1 3 4 6
输出:
72
24
18
12
解析：先求出前缀积和后缀积，然后分别求出Pi，详见代码：
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int z[100005];
int d[100005];
int main()
{
int n;
cin>>n;
z[0]=1;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
z[i]=(z[i-1]*a[i])%10000;//求前缀积
}
d[n+1]=1;
for (int i=n;i>0;i--){
d[i]=(d[i+1]*a[i])%10000;//求后缀积
}
for (int i=1;i<=n;i++){
int t;
t=(z[i-1]*d[i+1])%10000;//求Pi
printf("%d\n",t);
}
return 0;
}