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;
}