15陕西省赛——数学题——n维空间切d刀共能分成多少份？？？

秦总给我看的题。。。

题目的大意如题目所示，再次感觉数学的薄弱。。。0<n<100000,0<d<1000000,首先dp[n][d] = dp[n][d-1] + dp[n-1][d-1]],这个递推式很好推，然后复杂度是o(n*d)肯定过不了的，然后就是两个方向搞了，一个就是优化，还有一个就是直接通项，一开始先是搞了一顿通项，结果表示这个好像有点难度，然后再搞优化，可不可以把d二分来搞，这个时候每一项还要再加上一块，想了想还是搞不定。然后再回头搞通项，因为是考试前一天搞的，搞了一会就直接百度有没有通项了，（orz那些在5个小时里面能够推出通项的大牛。。。）附上链接 http://www.zhihu.com/question/29837521

点击打开链接

当n >= d时，dp[n][d] = 2^d，这个比较好理解。

n < d时，这个公式的推导过程看知乎大神的回答就好了，因为MOD = 10e9+7，是一个质数，所以求逆元的时候直接上线性的做法。

然后这道题就解决了。。。

附上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define FOR(i,x,y)  for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define ll  long long
#define N   111111
#define D   1111111
#define MOD 1000000007

using namespace std;

ll c[N],mu[N];
ll n,d;

ll quickpow(ll a,ll n,ll m){
    ll ans=1;
    while(n){
        if(n&1) ans = (ans*a)%m;
        a = (a*a)%m;
        n>>=1;
    }
    return ans;
}

void ex_gcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b)  {d = a;x = 1;y = 0;return;}
    ex_gcd(b,a%b,d,y,x);
    y -= x*(a/b);
}
/**
ll inv(ll a,ll n){
    ll d,x,y;
    ex_gcd(a,n,d,x,y);
    return d == 1 ? (x+n)%n : -1;
}

void init(){
    FOR(i,1,N){
        mu[i] = inv(i,MOD);
    }
}
**/
//在线性时间内求质数的逆元
void init(){
    mu[1] = 1;
    FOR(i,2,N){
        mu[i] = mu[MOD%i] *(MOD-MOD/i)%MOD;
    }
}

void C(){
    c[0] = 1;
    FOR(i,1,n+1){
        ll tem = (d+1-i)*mu[i]%MOD;
        c[i] = (tem*c[i-1]) % MOD;
    }
}

ll solve(){
    ll res = 0;
    FOR(i,0,n+1){
        res += c[i];
        res %= MOD;
    }
    return res;
}

int main()
{
    freopen("test.in","r",stdin);
    int t,tCase = 0;
    scanf("%d",&t);
    init();
    while(t--){
        printf("Case #%d: ",++tCase);
        scanf("%lld%lld",&n,&d);
        ll ans = 0;
        if(n >= d){
            ans = quickpow(2,d,MOD);
        }
        else{
            C();
            ans = solve();
        }
        printf("%lld
",ans);
    }
    return 0;
}