当前位置:网站首页>AcWing 886. Finding combinatorial number II (pretreatment factorial)
AcWing 886. Finding combinatorial number II (pretreatment factorial)
2022-07-01 04:51:00 【MangataTS】
Topic link
https://www.acwing.com/problem/content/description/888/
Ideas
This data range is even larger , So we can't use recursion at this time , Because I can't save it , Second, the complexity is too high , So we can start from the definition of combinatorial number : C a b = a ! ( a − b ) ! × b ! C_a^b=\frac{a!}{(a-b)!\times b!} Cab=(a−b)!×b!a!, So now we just need to 1e5 All factorials within and the inverse preprocessing of factorials are OK , So the problem is solved
Code
#include<bits/stdc++.h>
using namespace std;
//---------------- Custom part ----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
int dx[4] = {
-1, 0, 1, 0}, dy[4] = {
0, 1, 0, -1};
ll ksm(ll a,ll b) {
ll ans = 1;
for(;b;b>>=1LL) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
ll lowbit(ll x){
return -x & x;}
const int N = 2e6+10;
//---------------- Custom part ----------------
ll t,n,m,q,fact[N],invfact[N];
void init(){
invfact[0]= fact[0] = 1;// initialization
for(int i = 1;i < N; ++i) {
fact[i] = fact[i-1] * i % mod;
invfact[i] = ksm(fact[i],mod-2);
}
}
void slove(){
ll a,b;
cin>>a>>b;
cout<<(fact[a] * invfact[a-b]) % mod * invfact[b] % mod <<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
init();
cin>>t;
while(t--){
slove();
}
return 0;
}
边栏推荐
- Pytoch (III) -- function optimization
- [daily question in summer] first time, second time, deal!
- [daily question in summer] Luogu p1568 race
- 分布式事务-解决方案
- Pytorch(一) —— 基本语法
- Solve the problem that the external chain file of Qiankun sub application cannot be obtained
- [daily question in summer] Luogu p5740 [deep foundation 7. Example 9] the best student
- Kodori tree board
- 【暑期每日一题】洛谷 P5740【深基7.例9】最厉害的学生
- The longest increasing subsequence and its optimal solution, total animal weight problem
猜你喜欢
[hard ten treasures] - 2 [basic knowledge] characteristics of various topological structures of switching power supply
Pytorch(二) —— 激活函数、损失函数及其梯度
Distributed transactions - Solutions
Basic skeleton of neural network nn Use of moudle
Cmake selecting compilers and setting compiler options
神经网络-最大池化的使用
RuntimeError: mean(): input dtype should be either floating point or complex dtypes.Got Long instead
Principle, technology and implementation scheme of data consistency in distributed database
分布式全局唯一ID解决方案详解
STM32 photoresistor sensor & two channel AD acquisition
随机推荐
分布式事务-解决方案
[daily question in summer] Luogu p5740 [deep foundation 7. Example 9] the best student
Use and modification of prior network model
每日一题-LeetCode1175-质数排列-数学
Serialization and deserialization of objects
Introduction to JVM stack and heap
神经网络-使用Sequential搭建神经网络
VIM简易使用教程
How to use common datasets in pytorch
神经网络-卷积层
Principle, technology and implementation scheme of data consistency in distributed database
解决:拖动xib控件到代码文件中,报错setValue:forUndefinedKey:this class is not key value coding-compliant for the key
【暑期每日一题】洛谷 P5886 Hello, 2020!
【暑期每日一题】洛谷 P3742 umi的函数
Pico neo3 handle grabs objects
Summary of testing experience - Testing Theory
Several methods of creating thread classes
RuntimeError: mean(): input dtype should be either floating point or complex dtypes. Got Long instead
Pytoch (I) -- basic grammar
[hard ten treasures] - 2 [basic knowledge] characteristics of various topological structures of switching power supply