[前缀和]aw3574.乘积数量(前缀和+组合数学)

1. 题目来源

链接&＃xff1a;3574. 乘积数量

2. 题目解析

所有方案满足等差数列求和公式&＃xff0c;故所有方案数为 n(1&＃43;n)/2。会爆 int 注意开 long long。

dp 解法&＃xff1a;

• f[i][0] 表示以 i 结尾的正数索引的方案数
• f[i][1] 表示以 i 结尾的负数索引的方案数
• 答案需要累加 i: 1~n

#include using namespace std;typedef long long LL;const int N &＃61; 2e5&＃43;5;int n;
LL f[N][2]; int main() {scanf("%d", &n);for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; ) {int x;scanf("%d", &x);if (x > 0) {f[i][0] &＃43;&＃61; f[i - 1][0] &＃43; 1; f[i][1] &＃43;&＃61; f[i - 1][1];} else {f[i][0] &＃43;&＃61; f[i - 1][1];f[i][1] &＃43;&＃61; f[i - 1][0] &＃43; 1;}}LL a &＃61; 0, b &＃61; 0;for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; )a &＃43;&＃61; f[i][1], b &＃43;&＃61; f[i][0];printf("%lld %lld\n", a, b);return 0;
}


前缀和解法&＃xff1a;

这里理解为前缀乘积更加容易。

前缀和 s[i] 表示前 i 个数的乘积&＃xff0c;注意 s[0] &＃61; 1。

则 s[r] / s[l - 1] 就是区间 a[l ~ r] 的乘积。我们只关心正负&＃xff0c;故仅需要存前缀和数组 s[i] 的正负即可。

针对一个 s[i] 以 i 结尾的区间&＃xff0c;我们只需要知道 s[i] 的正负&＃xff0c;针对任一一个区间 [j, i] 那么有区间乘积为 s[i]/s[j-1]。s[i] 的正负确定&＃xff0c;只需知道 0~i-1 之间的分别的正负和即可。

#include using namespace std;typedef long long LL;const int N &＃61; 2e5&＃43;5;int n;
int sa, sb &＃61; 1; // 0~i-1 之间的 负 正 数个数&＃xff0c;注意 s[0] 的符号是正&＃xff0c;初始 sb 就有一个值&＃xff0c;代表 s[0] 的符号为正
LL a, b; // a 为负方案数&＃xff0c;b 为正方案数int main() {scanf("%d", &n);int s &＃61; 1;for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; ) {int x;scanf("%d", &x);if (x < 0) s *&＃61; -1;if (s < 0) a &＃43;&＃61; sb, b &＃43;&＃61; sa, sa &＃43;&＃43; ;else a &＃43;&＃61; sa, b &＃43;&＃61; sb, sb &＃43;&＃43; ;}printf("%lld %lld\n", a, b);return 0;
}


数学解法&＃xff1a;

大佬题解链接&＃xff1a;

#include
#include
#include using namespace std;typedef long long LL;const int N &＃61; 2e5 &＃43; 10;
int n;
int s[N];
int s0, s1; //s0统计前缀和为偶数的个数&＃xff0c;s1统计前缀和为奇数的个数int main()
{cin >> n;s0 &＃43;&＃43; ; //s[0]是偶数&＃xff0c;直接加进去&＃xff0c;省掉额外迭代一轮的操作for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43; i){int x;cin >> x;s[i] &＃61; s[i - 1] &＃43; (x < 0);if (s[i] & 1) &＃43;&＃43; s1;else &＃43;&＃43; s0;}cout << (LL)s0 * s1 << " " << (LL)s0 * (s0 - 1) / 2 &＃43; (LL)s1 * (s1 - 1) / 2 << endl;return 0;
}