当前位置:网站首页>AcWing 889. 01 sequence satisfying the condition (Cartland number)
AcWing 889. 01 sequence satisfying the condition (Cartland number)
2022-07-01 04:51:00 【MangataTS】
Topic linking
https://www.acwing.com/problem/content/891/
Ideas
Because there is n individual 1 and n individual 0, Then we can finally reach the point (n,n), It's hard for us to think positively , So we can see in the middle 1 The quantity ratio of 0 In many cases , For this method, we can turn it into a plane diagram ,1 It means taking a step to the right ,0 It means taking a step up , Then the opposite of what we are asking for now is to go through y = x + 1 y=x+1 y=x+1 The number of schemes for this line , We can do to this line (n,n) A symmetric graph of the is (n-1,n+1), We will find that the number of schemes in this position is : C 2 n n − 1 C_{2n}^{n-1} C2nn−1, For walking to (n,n) The number of all schemes is : C 2 n n C_{2n}^{n} C2nn, Then let's just make a difference , After simplification is :
C 2 n n n + 1 \frac{C_{2n}^{n}}{n+1} n+1C2nn This number is also known as the Cartland number
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll ksm(ll a,ll b){
ll res = 1;
for(;b;b>>=1,a=a*a%mod) if(b & 1) res = res * a % mod;
return res;
}
ll C(ll a,ll b){
b = min(a-b,b);
ll ansL = 1,ansR = 1;
for(int i = 1;i <= b; ++i){
ansL = ansL * (a-i+1) % mod;
ansR = ansR * i % mod;
}
ll ans = ansL * ksm(ansR,mod-2) % mod;
return ans;
}
ll slove(ll n){
return (C(2*n,n)-C(2*n,n-1) + mod) % mod;
}
int main()
{
ll a;
scanf("%lld",&a);
printf("%lld\n",slove(a));
return 0;
}
边栏推荐
- [FTP] the solution to "227 entering passive mode" during FTP connection
- LeetCode316-去除重复字母-栈-贪心-字符串
- Buffer stream and transform stream
- Shell之Unix运维常用命令
- Why is Internet thinking not suitable for AI products?
- 【暑期每日一题】洛谷 P7222 [RC-04] 信息学竞赛
- FileInputStream
- Leecode question brushing record 1332 delete palindrome subsequence
- RuntimeError: “max_pool2d“ not implemented for ‘Long‘
- 分布式-总结列表
猜你喜欢
STM32 光敏电阻传感器&两路AD采集
最长递增子序列及最优解、动物总重量问题
One click shell to automatically deploy any version of redis
神经网络-非线性激活
Neural network - nonlinear activation
VIM easy to use tutorial
AssertionError assert I.ndim == 4 and I.shape[1] == 3
Manually implement a simple stack
AssertionError assert I.ndim == 4 and I.shape[1] == 3
STM32扩展板 数码管显示
随机推荐
STM32 extended key scan
Pytorch(四) —— 可视化工具 Visdom
Pytoch (I) -- basic grammar
Technology sharing | broadcast function design in integrated dispatching
LeetCode316-去除重复字母-栈-贪心-字符串
Neural networks - use sequential to build neural networks
LeetCode1497-检查数组对是否可以被 k 整除-数组-哈希表-计数
Codeworks round 449 (Div. 1) C. Kodori tree template
RDF query language SPARQL
Pytorch convolution operation
[hard ten treasures] - 2 [basic knowledge] characteristics of various topological structures of switching power supply
RuntimeError: “max_pool2d“ not implemented for ‘Long‘
Basic skeleton of neural network nn Use of moudle
Basic usage, principle and details of session
Openresty rewrites the location of 302
C#读写应用程序配置文件App.exe.config,并在界面上显示
[hard ten treasures] - 1 [basic knowledge] classification of power supply
神经网络-非线性激活
LeetCode_ 66 (plus one)
Common methods in transforms