文档章节

Codeforces Gym - 101147G The Galactic Olympics

o
 osc_x4rg8g6r
发布于 2018/04/23 18:41
字数 551
阅读 30
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

Discription

Altanie is a very large and strange country in Mars. People of Mars ages a lot. Some of them live for thousands of centuries!

Your old friend Foki "The president of the Martian United States of Altanie" is the oldest man on Mars. He's very old no one knows how old he is! Foki loves children, so, he had (0 < K ≤ 106) children!

The government in Altanie decided to send a team of athletes to Venus. To participate in (0 < N ≤ 103) different game in the Galactic Olympics. So Foki told them to send his children instead!

Foki is in a big problem. How can he decide whom of his children is going to participate in which game, at the same time his children must participate in all the games and every one of his children get to participate in at least one game?

Note that in a certain arrangement, each one of Foki's children can participate in multiple games in the Olympics, but each game must be arranged to exactly one player.

Your job is to help Foki and answer his question: in how many way can he arrange his children to the games in Venus Olympics while satisfying the previous two conditions.

Input

The first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 103 ) the number of the games in the Olympics, ( 0 < K ≤ 106 ) the number of Foki's children.

Output

For each test case print one line contains the answer to Foki's question. Since the answer is very large. Print the answer modulo 109 + 7

Example

Input
1
3 2
Output
6


首先每个人至少要参加一个项目,并且一个项目最多只能属于一个人,所以我们可以很容易的建出模型: 有n个不同的物品,我们要把它们分别放入k个有序的集合,并且要求每个集合至少要有一个物品,求方案总数。
我们知道,当集合无序的时候,方案数就是 S(n,k) ,即第二类斯特林数的第n行第k列的值; 集合有序的时候,再乘上 k! 就行了。


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1000000007;
const int maxn=1005;
int T,n,m,S[maxn][maxn],jc[maxn];
inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void init(){
	S[0][0]=jc[0]=1;
	for(int i=1;i<=1000;i++){
		jc[i]=jc[i-1]*(ll)i%ha;
	    for(int j=1;j<=i;j++) S[i][j]=add(S[i-1][j-1],S[i-1][j]*(ll)j%ha);
	}
}
int main(){
	freopen("galactic.in","r",stdin);
	init(),scanf("%d",&T);
	while(T--) scanf("%d%d",&n,&m),printf("%d\n",n<m?0:(int)(S[n][m]*(ll)jc[m]%ha));
	return 0;
}

  

 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
基于通信的人工智能环境--CommAI-env

CommAI-env(基于通信的人工智能环境(Environment for Communication-based AI))是一个用于训练和评估人工智能的平台。其使用了一个基于通信(communication)的设置,其中它可以通过一个...

匿名
2016/10/05
876
0
拉美的Facebook Quepasa一亿美元收购myyearbook

发布时间: 2011-7-21 来源: techcrunch.com 编译:GBin1.com Quepasa,拉丁用户中的Facebook耗资1亿美元成功合并了社交网站公司myyearbook。包括8200万股票了1800万现金。 募集到1700万的基...

gbin1
2011/07/22
676
3
20 个新鲜的免费图标集

Free Mac Icons Theme for Retina Display or iPhone 4 Genesis Theme for iPhone 4 Genesis for iPad Icons 5 Free PSD Stickers Lamond. 70 icons Gur project Q-oob for SuperBar Build I......

小编辑
2012/01/24
723
3
自动蹭饭工具-food-bot

一大早看到这个zt真是赶脚异常的欢乐啊,哈哈哈 今天和我们CMU的同学聊天,知道了真geek的生活是怎么样的。当年有个师弟天天耽于课程,一 学期就回了3次家,期末幡然醒悟果断把房子退了,天天...

蟋蟀哥哥
2012/08/29
2.6K
16
Android 日历提供器(三)

日历的Intent对象 你应用程序不需要读写日历数据的权限,它可以使用Android的Calendar应用程序支持的Intent对象来替代你的应用程序的读写权限。下表列出了Calendar提供器支持的Intent对象: ...

长平狐
2012/10/16
745
0

没有更多内容

加载失败,请刷新页面

加载更多

一年Node.js开发开发经验总结

写在前面 不知不觉的,写Node.js已经一年了。不同于最开始的demo、本地工具等,这一年里,都是用Node.js写的线上业务。从一开始的Node.js同构直出,到最近的Node接入层,也算是对Node开发入门...

osc_2fb62vw0
18分钟前
0
0
详解斜率优化

详解斜率优化 斜率优化的话前几个月学过一次,然后感觉会了,结果今天遇到个题,比赛时花了1h硬敲没怼出来,然后又去看了看人家的讲解,加上自己疯狂yy,才发现(原来很水嘛)上次只是略懂皮...

osc_eumlh0pn
19分钟前
0
0
pytest文档46-关于https请求警告问题(InsecureRequestWarning: Unverified HTTPS request is being made)

前言 使用 pytest 执行 https 请求用例的时候,控制台会出现警告:InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised......

osc_8s3utzxr
20分钟前
8
0
进程间通信和线程间通信的几种方式

进程间通信和线程间通信的几种方式 进程、线程、协程之概念理解 进程和线程、协程的区别 进程 进程(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的...

osc_we9lokaj
21分钟前
0
0
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010。

给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010...

osc_kedi1mvz
21分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部