本文共 1922 字，大约阅读时间需要 6 分钟。

题目

Description

情人节之际，Alex决定用K种珍珠为他的GF做一串举世无双的珍珠垂饰与她的项链相配。珍珠垂饰是由珍珠连接而成的，其长度可以认为就是珍珠垂饰上珍珠的个数。众所周知，Alex家缠万贯，每种珍珠他都拥有N颗。根据将珍珠垂饰打开后珍珠不同的排列顺序可以区别不同种类的项链。现在，他好奇自己可以组成多少种长度为1至N的不同的珍珠垂饰？当然，为显富有，每串珍珠垂饰都要必须由K种珍珠连成。

Input

输入包含多组数据。第一行是一个整数T，表示测试数据的个数。每组数据占一行，包含两个整数N和K，用一个空格隔开。

Output

每组数据输出仅一行，为项链的种类数。

Sample Input

2

Sample Output

2

Data Constraint

1 <= T <= 10

题解

题意

对于每个$i（1\le i\le n）$，求出用$k$种珍珠组成的方案数（每种珍珠必须用上），求和，答案取模1234567891。

分析

如果没有$k$这个限制

Code

#include
   
    #define mod 1234567891using namespace std;int i,j,fh,t,n,k;long long power,ny,ans,c[32][32];long long ksm(long long x,long long y){   	long long s;	s=1;	while (y>0)	{   		if (y&1) s=s*x%mod;		y>>=1;		x=x*x%mod;	}	return s;}int main(){   	c[0][0]=1;	for (i=1;i<=31;i++)		for (j=1;j<=i;j++)			c[i][j]=c[i-1][j-1]+c[i-1][j];	scanf("%d",&t);	while (t--)	{   		ans=0;		fh=1;		scanf("%d%d",&n,&k);		if (k==1)	printf("%d\n",n);		else		{   			for (i=k;i>=1;i--)			{   				power=ksm(i,n+1);				printf("%lld %lld\n",c[k+1][k-i+1],power);				if (i==1) 				{   					ans=(ans+fh*n*c[k+1][k-i+1]%mod)%mod;					fh=-fh;				}				else 				{   					ny=ksm(i-1,mod-2);					ans=((c[k+1][k-i+1]*((power-i+mod)*ny%mod)%mod)*fh+ans)%mod;					fh=-fh;					printf(	"%lld\n",(ans+mod)%mod);				}			}					printf(	"%lld\n",(ans+mod)%mod);			}	}	return 0;}