AcWing 306. 杰拉尔德和巨型象棋计数类DP

2021-03-12 08:30

阅读：521

标签：efi 计数 return namespace nfa turn clu https 容斥原理

参考秦大佬的题解： https://www.acwing.com/solution/AcWing/content/1730/


//通过容斥原理
//那么F[i]表示为从左上角走到第i个黑色格子,而且途中不经过其他黑色格子的方案数 
//终点作为第k+1个黑格子

//F[i]=(1,1)到(xi,xj)的总方案数-前(i-1)黑格方案数*黑格到(xi,yi)的方案数 
//其中， (1,1)到(xi,xj)的总方案数为C(xi-1+yi-1,xi-1)
 
#include
#include
#define int long long
using namespace std;
const int N=200020;
const int mod=1e9+7;
int n,m,k;
int fact[N], infact[N];
pairdate[N]; 
int f[N];
typedef long long LL;
int qmi(int a,int k,int p)
{
    int res=1%p;
    while(k)
    {
        if(k&1) 
			res=res*a%p;
        a=a*a%p;
        k >>= 1;
    }
    return res;
}
int C(int a,int b)
{
	return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
signed main()
{
	cin>>n>>m>>k;
    for(int i=1;i>date[i].first>>date[i].second;
    fact[0]=infact[0]=1;
    for(int i=1;i

AcWing 306. 杰拉尔德和巨型象棋计数类DP

标签：efi 计数 return namespace nfa turn clu https 容斥原理

原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12601042.html

上一篇：windows字符集

下一篇：Win10应用商店打不开的解决办法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 306. 杰拉尔德和巨型象棋计数类DP
文章链接：http://soscw.com/essay/63602.html

亲，登录后才可以留言！

AcWing 306. 杰拉尔德和巨型象棋计数类DP

参考秦大佬的题解： https://www.acwing.com/solution/AcWing/content/1730/

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 306. 杰拉尔德和巨型象棋 计数类DP

参考秦大佬的题解： https://www.acwing.com/solution/AcWing/content/1730/

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 306. 杰拉尔德和巨型象棋计数类DP