卧薪尝胆,厚积薄发。
Date: Fri Aug 24 10:39:21 CST 2018 In Category: NoCategory

Description:

在 $n\times m$ 的棋盘上摆车,要求两两不能攻击,且上面的要在下面的左边,求方案数。
$1\le n,m \le 1000000$

Solution:

答案就是 $C_m^n(n>m)$ ,统计质因子即可。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
#define MAXN 1000001
int prime[MAXN],tot = 0;
int pr[MAXN];
bool isprime[MAXN];
int mindiv[MAXN];
int cnt[MAXN];
struct bigint
{
int a[100];
int l;
bigint(){l = 1;a[1] = 1;}
friend bigint operator * (bigint x,int y)
{
for(int i = 1;i <= x.l;++i)
{
x.a[i] *= y;
}
for(int i = 1;i <= x.l;++i)
{
x.a[i + 1] += x.a[i] / 10;
x.a[i] %= 10;
}
while(x.a[x.l + 1] > 0)
{
++x.l;
x.a[x.l + 1] += x.a[x.l] / 10;
x.a[x.l] %= 10;
}
if(x.l > 50)
{
for(int i = 50 + 1;i <= x.l;++i)x.a[i] = 0;
x.l = 50;
}
while(x.a[x.l] == 0)--x.l;
return x;
}
}t;
void pt(bigint k)
{
for(int i = k.l;i >= 1;--i)
{
printf("%d",k.a[i]);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
if(n < m)swap(n,m);
for(int i = 2;i <= n;++i)isprime[i] = true;
for(int i = 2;i <= n;++i)
{
if(isprime[i])
{
prime[++tot] = i;
mindiv[i] = i;
pr[i] = tot;
}
for(int j = 1;j <= tot && i * prime[j] <= n;++j)
{
isprime[i * prime[j]] = false;
mindiv[i * prime[j]] = prime[j];
if(i % prime[j] == 0)break;
}
}
for(int i = 1;i <= n;++i)
{
int k = i;
while(k != 1)
{
++cnt[pr[mindiv[k]]];
k /= mindiv[k];
}
}
for(int i = 1;i <= m;++i)
{
int k = i;
while(k != 1)
{
--cnt[pr[mindiv[k]]];
k /= mindiv[k];
}
}
for(int i = 1;i <= n - m;++i)
{
int k = i;
while(k != 1)
{
--cnt[pr[mindiv[k]]];
k /= mindiv[k];
}
}
for(int i = 1;i <= tot;++i)
{
for(int j = 1;j <= cnt[i];++j)
{
t = t * prime[i];
}
}
pt(t);
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡