当前位置:网站首页>AcWing 885. Find the combination number I (recursive preprocessing)
AcWing 885. Find the combination number I (recursive preprocessing)
2022-07-01 04:51:00 【MangataTS】
Problem plane connection
https://www.acwing.com/problem/content/887/
Ideas
Through the knowledge of combinatorial mathematics, we can know C a b = C a − 1 b + C a − 1 b − 1 C_a^b = C_{a-1}^b + C_{a-1}^{b-1} Cab=Ca−1b+Ca−1b−1 Of , The right side of the equation is from a − 1 a-1 a−1 Choose from the number of b − 1 b-1 b−1 Number and from a − 1 a-1 a−1 Choose from the number of b b b Number of cases , Corresponding to the current b b b Number of options and no options ( It seems to be a little similar to the idea of backpack ), Then we can get the result by recursion 2000 All combinations within , See code for details
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 = 2e3+10;
//---------------- Custom part ----------------
ll t,n,m,q,c[N][N];
void init(){
for(int i = 0;i < N; ++i) c[i][0] = 1;// Initialization selection 0 The situation of
for(int i = 1;i < N; ++i) {
for(int j = 1;j <= i; ++j) {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
}
}
void slove(){
ll a,b;
cin>>a>>b;
cout<<c[a][b]<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
init();
cin>>t;
while(t--){
slove();
}
return 0;
}
边栏推荐
- Basic skeleton of neural network nn Use of moudle
- 分布式全局唯一ID解决方案详解
- RuntimeError: mean(): input dtype should be either floating point or complex dtypes. Got Long instead
- Leecode question brushing record 1332 delete palindrome subsequence
- Difficulties in the development of knowledge map & the importance of building industry knowledge map
- Basic exercise of test questions hexadecimal to decimal
- 【硬十宝典】——2.【基础知识】开关电源各种拓扑结构的特点
- [daily question in summer] Luogu p1568 race
- C read / write application configuration file app exe. Config and display it on the interface
- 【暑期每日一题】洛谷 P1568 赛跑
猜你喜欢
随机推荐
Data loading and preprocessing
Matters behind the construction of paint testing laboratory
Basic usage, principle and details of session
FileOutPutStream
LeetCode_35(搜索插入位置)
分布式数据库数据一致性的原理、与技术实现方案
Basic exercise of test questions hexadecimal to decimal
1076 Forwards on Weibo
无器械健身
[daily question in summer] Luogu p2026 find the analytic formula of primary function
科研狗可能需要的一些工具
技术分享| 融合调度中的广播功能设计
Leecode records the number of good segmentation of 1525 strings
VIM easy to use tutorial
【暑期每日一题】洛谷 P5886 Hello, 2020!
How to do the performance pressure test of "Health Code"
【FTP】FTP连接时出现“227 Entering Passive Mode”的解决方法
【暑期每日一题】洛谷 P1568 赛跑
RuntimeError: “max_pool2d“ not implemented for ‘Long‘
The design points of voice dialogue system and the importance of multi round dialogue