light oj 1102 - Problem Makes Problem组合数学(隔板法)
As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15 solutions. They are
1. 0 0 4
2. 0 1 3
3. 0 2 2
4. 0 3 1
5. 0 4 0
6. 1 0 3
7. 1 1 2
8. 1 2 1
9. 1 3 0
10. 2 0 2
11. 2 1 1
12. 2 2 0
13. 3 0 1
14. 3 1 0
15. 4 0 0
As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.
Input
Input starts with an integer T (≤ 25000), denoting the number of test cases.
Each case contains two integer n (0 ≤ n ≤ 106) and k (1 ≤ k ≤ 106).
Output
For each case, print the case number and the result modulo 1000000007.
Sample Input |
Output for Sample Input |
4 4 3 3 5 1000 3 1000 5 |
Case 1: 15 Case 2: 35 Case 3: 501501 Case 4: 84793457 |
分析:
题目意思是把 n个元素分成k组且允许有空位置, 这就用到隔板法中的允许若干个人(或位置)为空的问题, 因为把元素分成k组需要k-1个隔板,并且可以允许元素个数为空,所以隔板可以放在任意位置,隔板加上元素个数一共有n+k-1个位置,那么就相当于从n+k-1个位置中选出k-1个位置放隔板即c(n-k+1, k-1)。然后直接用费小马定理(a/b)%mod = a * (b(^mod-2))%mod;求下逆元就可以了。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define N 2000010
#define mod 1000000007
using namespace std;
long long d[N];
void init()
{
d[0] = 1;
for(int i = 1; i < N; i++)
d[i] = (i * d[i-1]) % mod;
}
long long quickmi(long long a, long long b)
{
long long sum = 1;
while(b)
{
if(b & 1)
sum = (sum * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return sum;
}
int main(void)
{
int T , cas;
int n, k;
scanf("%d", &T);
init();
cas = 0;
while(T--)
{
cas++;
scanf("%d%d", &n, &k);
long long ans = quickmi((d[k-1] * d[n]) % mod, mod-2);
ans = (d[n+k-1] * ans ) % mod;
printf("Case %d: %lld\n", cas, ans);
}
return 0;
}
最新文章
- 让我们来谈谈JDBC
- 转发 VS 重定向
- css异常
- 基于Ionic2的开源项目
- Chap4: question: 19 - 28
- Uiautomator自动编译运行脚本
- 解决 SQL Server Profiler 跟踪[不断]出现检索数据
- 用正则表达式替换html标签
- Top 10 Free Wireless Network hacking/monitoring tools for ethical hackers and businesses
- JavaWeb学习记录(十九)——开发JSTL自定义标签
- liux之sed用法
- client|server 最简单的聊天
- 用qsort排序
- 1-安装MQTT服务器(Windows)
- 《深入实践Spring Boot》阅读笔记之三:核心技术源代码分析
- Android使用scrollview截取整个的屏幕并分享微信
- QT和MFC的差别
- 《算法》第四章部分程序 part 18
- 初识node.js(通过npm下载项目依赖的包的过程)
- SeaJS 与 RequireJS 的差异对比