Easy Equation【差分+前缀和】

题意

给出 (4) 个整数：(a,b,c,d)，求出满足方程:(x+y+z=k) 的方案数，其中：(0leq x leq a,0leq y leq b,0 leq z leq c,0leq k leq d)。
(0leq a,b,c,d leq 10^6)
题目链接：https://ac.nowcoder.com/acm/contest/8688/A

分析

先求出 (x+y=i) 的方案数，然后将 (x+y=i) 视作一个数，求出 (i+z) 的方案数，然后枚举 (k) 的范围，求出答案。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 4e6 + 5;
ll f1[N], f2[N];

int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    for (int i = 0; i <= a;i++)//求出x+y的方案数
    {
        f1[i] += 1;
        f1[i + b + 1] -= 1;
    }
    f1[0] = 1;
    for (int i = 1; i <= a + b;i++)//i=x+y时的方案数
        f1[i] += f1[i - 1];
    for (int i = 0; i <= a + b;i++)
    {
        f2[i] += f1[i];
        f2[i + c + 1] -= f1[i];
    }
    f2[0] = 1;
    for (int i = 1; i <= a + b + c;i++)
        f2[i] += f2[i - 1];
    ll ans = 0;
    for (int i = 0; i <= d;i++)
        ans += f2[i];
    printf("%lld
", ans);
    return 0;
}