「PMOI-1」抽奖

· · 题解

令 F(t) 表示抽了 t 张体验卡的情况数。 那么答案就是 \sum_{t=0}^n F(t)，那我们只需求出所有 F(t) 如果考虑先抽 t 张卡，再看有多少种卡可以选话，这样实际上是很难知道哪些种类的卡已经抽到。所以转换思路，考虑先选定卡再抽，这样就能保证选的卡一定是抽到了的。

F(t)=m^t+m\sum_{i=1}^t \binom{t}{i} (m-1)^{t-i}

组合意义即为，不选的情况数——每张卡都能随便抽，加上选卡的情况数——卡的种类 \times 枚举抽到了多少选的卡的那个种类的卡 \times 这些卡是在哪几次抽到的 \times 剩下的随便抽 容易发现这个式子可以化简

F(t)=m^t+m(-t^{m-1}+\sum_{i=0}^t \binom{t}{i} (m-1)^{t-i} 1^i)=m^t+m(-(m-1)^t+m^t)

所以答案就是

\sum_{t=0}^n F(t)=\sum_{t=0}^n m^t+\sum_{t=0}^n m^{t+1}-m\sum_{t=0}^n (m-1)^t

容易发现就是三个等比数列，随便求一下和即可。

#include<stdio.h>
#define ll long long
#define N 100007
#define Mod 1000000007

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

ll qpow(ll x,ll y){
    ll ret=1,cnt=0;
    while(y>=(1LL<<cnt)){
        if(y&(1LL<<cnt)) ret=(ret*x)%Mod;
        x=(x*x)%Mod,cnt++;
    }
    return ret;
}

ll calc(ll x,ll y){
    if(!x) return 1;
    if(x==1) return (y+1)%Mod;
    return (qpow(x,y+1)-1+Mod)%Mod*qpow((x-1+Mod)%Mod,Mod-2)%Mod;
}

int main(){
    int T=read();
    while(T--){
        ll n=read(),m=read();
        ll ans=(calc(n,m)+calc(n,m+1)-1-n*calc(n-1,m)%Mod+Mod)%Mod;
        printf("%lld\n",ans);
    }
}