ABC156E Roaming 题解

题目链接：ABC156E Roaming

题意：

翻译来自我们模拟赛，可能和原题有区别

输入两个数字 \(n,k\) ，初始时有 \(n\) 个盒子，每个盒子中都装着一个小球，\(n\) 个小球之间不可区分。现在你要进行下列操作恰好 \(k\) 次

• 选择任意一个盒子中的一个小球，将它放到一个不同的盒子中

你需要算出在 \(k\) 次操作之后，小球的不同的摆放方式有多少种，答案对 \(10^9+7\) 取模。两种摆放小球的方式被认为是不同的，当且仅当存在某一个盒子在两种摆放方式中放了不同个数的小球。

\(3 \le n \le 10^5,~2 \le k \le 10^9\)

Roundgod老师：这道题需要很好的观察能力

注意到 \(k \ge n-1\) 时方案数等于 \(n-1\) 的方案数

因为至多 \(n-1\) 步就可以摆出所有的情况，例如 5,0,0,0,0 只要 \(4\) 步

而步数是可以浪费的，比如本来要把 \(1\) 的一个球移到 \(2\) ，

可以先移到 \(3\) 再移到 \(2\) ，这样就浪费了一步，这样我们就可以把 \(k\) 步一直浪费到 \(n-1\) 步。

还有一个性质，如果某种情况 \(0\) 的个数小于等于 \(k\) ，那么一定可以达到，很显然。

• 当 \(k \ge n-1\) 时，答案为 \[ \dbinom{2n-1}{n-1} \]

  其实它就是 \(x_1+\dots + x_n=n\) ，\(x\) 的非负解个数

• 当 \(k<n-1\) 步时，答案为 \[ \sum_{i=0}^{k} \dbinom{n}{i}\dbinom{n-1}{n-i-1} \] 这里我们做的就是枚举 \(0\) 的个数。

  第一个是枚举 \(0\) 的位置，第二个是 \(x_1+\dots + x_{n-i}=n\) 的正整数解的个数

这个题稍微有点乱，因为性质很多，但是仔细思考一下还是颇有乐趣的。

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(4e5+15)

const int p=1e9+7;
int n,k,fac[N],invf[N];
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
int inv(int x){return qpow(x,p-2);}
void init()
{
    invf[0]=fac[0]=1;
    for(int i=1; i<=N-5; i++)
        fac[i]=fac[i-1]*i%p;
    invf[N-5]=inv(fac[N-5]);
    for(int i=N-5-1; i>=1; i--)
        invf[i]=invf[i+1]*(i+1)%p;
}
int A(int n,int k)
{
    if(n<k) return 0;
    return fac[n]*invf[n-k]%p;
}
int C(int n,int k)
{
    if(n<k) return 0;
    return fac[n]*invf[k]%p*invf[n-k]%p;
}
void add(int &x,int y){x+=y;if(x>=p)x-=p;}
void dec(int &x,int y){x-=y;if(x<0)x+=p;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init();
    cin >> n >> k;
    if(k>=n)return cout << C(2*n-1,n-1),0;
    int res=0;
    for(int i=0; i<=k; i++)
        add(res,C(n,i)*C(n-1,n-i-1)%p);
    cout << res;
    return 0;
}