首页 > 其他 > 详细

F - Problem Makes Problem (LightOJ - 1102)

时间:2018-02-14 15:23:20      阅读:31      评论:0      收藏:0      [点我收藏+]

标签:快速幂   stream   解题思路   ase   ble   oid   iostream   划分   pow   

- 题目大意

     求n有顺序的划分为k个数的方案数。

- 解题思路

    很显然是一个组合数,用隔板法, 再用费马小定理求逆元,再利用快速幂即可求出。

- 代码

#include<iostream>
#define mod 1000000007
using namespace std;
const int MAX = 2000000;
long long num[MAX];
void zh()
{
	num[0] = 1;
	for (int i = 1; i <MAX ; i++)
		num[i] = num[i - 1] * i%mod;
}
long long powMod(long long a, long long n) {
	long long ans = 1;
	for (; n > 0; n >>= 1)
	{ 
		if (n & 1) 
			ans = ans * a%mod; 
		a = a * a%mod;
	}
	return ans;
}
long long Comb(long long n, long long m) {
	if (n < m) 
		return 0;
	return num[n] * powMod(num[m] * num[n - m] % mod, mod - 2) % mod;
}

int main()
{
	int t;
	long long n, k;
	zh();
	cin >> t;
	for(int i=1;i<=t;i++)
	{
		cin >> n>> k;
		cout << "Case " << i << ": ";
		cout << Comb(n+k-1,k-1) << endl;
	}
	return 0;
}

  

F - Problem Makes Problem (LightOJ - 1102)

标签:快速幂   stream   解题思路   ase   ble   oid   iostream   划分   pow   

原文:https://www.cnblogs.com/alpacadh/p/8448358.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号