自动搬运

查看原文

来自洛谷，原作者为

	wwlw **

搬运于2025-08-24 22:29:03，当前版本为作者最后更新于2021-02-21 10:08:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

令 $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);
	}
}