LOJ6671 EntropyIncreaser 与 Minecraft 题解

题目链接：#6671. EntropyIncreaser 与 Minecraft

题意：

求方程 $\left|x_1\right|+\left|x_2\right|+\cdots+\left|x_n\right| \leq p$ 的整数解的组数。

输入格式

共一行, 包含两个正整数 $n, p\left(n \leq 10^6 ; p \leq 10^9\right)$ ，含义见题目描述。

输出格式：

输出一行一个整数, 表示方程的整数解的组数模 $10^9+7$ 的值。

注意到除了 $0$ 以外每个整数都会提供两次贡献，考虑枚举 $0$ 的个数 $n-k$ ，

那么剩下的数要求绝对值大于 $0$ ，这样方案数要先乘上符号位的 $2^k$ 。

设 $y_i = x_i + 1$ ，其中 $x_i \ge 0$ ，则需要求如下方程的方案数：

$$\sum_{i=1}^k y_i \leq p \Rightarrow \sum_{i=1}^k x_i \leq p-k$$

根据插板法，$\sum_{i=1}^{k}x_i=p$ 的方案数为 $\binom{k+p-1}{k-1}$ ，则总方案数为

$$\sum_{k = 0}^n \binom{n}{k}2^k\sum_{i=0}^p\binom{k+i-k-1}{k-1}$$

看上去要特判 $k=0$ 时答案为 $1$ 。那么我们继续化简

$$\sum_{k = 0}^n \binom{n}{k}2^k\sum_{i=0}^{p-1}\binom{i}{k-1}$$

因为 $\sum_{i=0}^n\binom{i}{m} = \binom{n+1}{m+1}$ 所以

$$\sum_{k=0}^n2^k\dbinom{n}{k}\dbinom{p}{k}$$

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
const int mod = 1e9 + 7;

int n,m,res=1,cur,inv[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; inv[1] = 1;
    res += cur = 2 * n * m % mod;
    for(int i = 2; i <= n; res += cur, i++)
    {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        cur = 2 * cur * (n - i + 1) % mod * (m - i + 1) % mod * inv[i] % mod * inv[i] % mod;
    }
    cout << res % mod << '\n';
    return 0;
}