米游社 · 崩坏:因缘精灵

5.5 组合计数(二)

来自版块: 酒馆
1
6
0
文章发表:08-10 最后编辑:08-10
来自合集: 算法提高课

299.车的放置

题目:

有下面这样的一个网格棋盘,a, b, c, d表示了对应边长度,也就是对应格子数。


当a=b=c=d=2时,对应下面这样一个棋盘:

要在这个棋盘上放k个相互不攻击的车,也就是这k个车没有两个车在同一行,也没有两个车在同一列,问有多少种方案。

只需要输出答案 mod 100003 后的结果。

输入格式

共一行,五个非负整数a, b, c, d, k。

输出格式

包括一个正整数,为答案 mod 100003后的结果。

数据范围

1≤a, b, c, d, k≤1000

保证至少有一种可行方案。

输入样例

2 2 2 2 2

输出样例

38

思路:

1.组合计数包括5.4的递推法,隔板法。以及加法原理,乘法原理,组合数,排列数。Lucas定理,Catalan序列等。

2.我们把这个图形分成两个规则图形。我们先考虑3×4的长方形,放2个车。由于不可以放一行,所以有C(3, 2)种。由于不可以放一列,第一个车可以放4列,第二个车只能放3列,为A(4, 2)种。更加一般的如果是n×m的矩形,则为C(n, k)×A(m, k)。我们把图形分成如下两半。

假设上半部分放i个车,则下半部分放k-i个车。我们这里需要先放上半部分,因为上半部分放完对下半部分的影响就确定了。但是如果先放下半部分,因为下半部分存在右边的凸出,所以分情况讨论更加复杂。所以我们先讨论上半部分。上半部分的情况数为C(b, i)×A(a, i)。对于下半部分,为C(d, k-i)×A(a+c-i, k-i)。总数即为∑(i=1→k)C(b, i)×A(a, i)×C(d, k-i)×A(a+c-i, k-i)。因为数据范围较小,我们可以选择任何一个正常的求组合数的方法。

代码(c++):

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2010, mod = 100003;

int fact[N], infact[N];

int qmi(int a, int k)

{

int res = 1;

while (k)

{

if (k & 1) res = (LL)res * a % mod;

a = (LL)a * a % mod;

k >>= 1;

}

return res;

}

int C(int a, int b) //C(a, b)的计算

{

if (a < b) return 0;

return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;

}

int P(int a, int b) //A(a, b)的计算

{

if (a < b) return 0;

return (LL)fact[a] * infact[a - b] % mod;

}

int main()

{

fact[0] = infact[0] = 1;

for (int i = 1; i < N; i ++ )

{

fact[i] = (LL)fact[i - 1] * i % mod;

infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod; //根据费马小定理,如果p是一个质数(此处p为100003,是质数),且a和p是互质的,则aᵖ⁻¹≡‌1 (mod p),所以a×aᵖ⁻²≡1 (mod p),所以a的乘法逆元为aᵖ⁻²。此处i为a,mod为p

}

int a, b, c, d, k;

cin >> a >> b >> c >> d >> k;

int res = 0;

for (int i = 0; i <= k; i ++ )

{

res = (res + (LL)C(b, i) * P(a, i) % mod * C(d, k - i) % mod * P(a + c - i, k - i)) % mod;

}

cout << res << endl;

return 0;

}


300.数三角形

题目:

给定一个n×m的网格,请计算三点都在格点上的三角形共有多少个。

下图为4×4的网格上的一个三角形。

注意:三角形的三点不能共线。

输入格式

输入一行,包含两个空格分隔的正整数m和n。

输出格式

输出一正整数,为所求三角形数量。

数据范围

1≤m, n≤1000

输入样例

2 2

输出样例

76

思路:

1.我们求出格点里选出3个点的方案数,再减去3个点在同一条直线上的方案数即是答案。如果把最左下的格点看成坐标原点,那么3个点连成直线走一下几种情况。

①斜率为0共有nC(m, 3)。

②斜率为+∞共有mC(n, 3)。

③斜率>0共有几种情况呢?。假设左下角的点和右上角的点横纵坐标差值分别为a, b,那么在n×m的矩形里这两个点一共有(n-a)×(m-b)种选法。最后一个点怎么求呢?


如图,假设右上角的点的坐标为(c, d),左下角为(i, j)。把它们两个点相连,那么第三个点必定在这个线段上,且坐标必须为整数。对于这个线段上的任何一个点(x, y)有y-j/x-i=d-j/c-i。则y=(d-j)(x-i)/(c-i)+j=[d-j/gcd(d-j, c-i)]/[c-i/gcd(d-j, c-i)]×(x-i)+b,x为正整数。

如果想使得y也为正整数,则必须使得c-i/gcd(d-j, c-i) | x-i。即x=[c-i/gcd(d-j, c-i)]×q+i。由于i≤x≤c,那么i≤[c-i/gcd(d-j, c-i)]×q+i≤c。解得0≤q≤gcd(d-j, c-i)。q可以为这个区间内任何一个整数,所以总数量为gcd(d-j, c-i)+1。又因为不能算上两个端点,所以总数为gcd(d-j, c-i)-1。即gcd(a, b)-1。

所以答案为∑(1≤i≤n, 1≤j≤m) [gcd(a, b)-1]×(n-a)×(m-b)种。

④斜率<0和③一样,为∑(1≤i≤n, 1≤j≤m) [gcd(a, b)-1]×(n-a)×(m-b)种。

代码(c++):

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

int gcd(int a, int b)

{

return b ? gcd(b, a % b) : a;

}

LL C(int n) //这里直接返回C(n, 3)即可

{

return (LL)n * (n - 1) * (n - 2) / 6;

}

int main()

{

int n, m;

cin >> n >> m;

n ++, m ++ ;

LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);

for (int i = 1; i <= n; i ++ )

for (int j = 1; j <= m; j ++ )

res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

cout << res << endl;

return 0;

}


301.序列统计

题目:

给定三个正整数N, L, R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。

输出答案对10⁶+3取模的结果。

输入格式

输入第一行包含一个整数T,表示数据组数。

第二到第T+1行每行包含三个整数N, L, R。

输出格式

输出包含T行,每行有一个数字,表示你所求出的答案对10⁶+3取模的结果。

数据范围

1≤N, L, R≤10⁹

1≤T≤100

输入数据保证L≤R

输入样例

2

1 4 5

2 4 5

输出样例

2

5

样例解释

对于第一组输入,满足条件的两个序列为{4},{5}。

思路:

1.对于第二组输入,满足条件的两个序列为{4},{5},{4,4},{4,5},{5,5}。本题我们枚举序列长度k,然后我们枚举序列长度k。因为本题要求数列的元素数值在[L, R]。所以我们可以做一个映射,映射为[0, R-L]。我们假设序列为a₁,……,aₖ,那么0≤a₁,……,aₖ≤R-L。就可以转化为上一题,x₁=a₁,x₂=a₂-a₁,……,xₖ=aₖ-aₖ₋₁。那么x₁+……+xₖ≤R-L。由于xᵢ≥0。那么就和之前的隔板法例题类似。由于隔板法的xᵢ不可以为0,所以我们继续映射,令yᵢ=xᵢ+1,这样可使得yᵢ>0。那么y₁+……+yₖ≤R-L+k。所以方案数为C(R-L+k, k)。这里和之前的题目有略微不同。因为这里是不等式,可以有剩余,我们设剩余为yₖ₊₁(yₖ₊₁≥0),使得y₁+……+yₖ+yₖ₊₁=R-L+k。所以放k个隔板,而不是k-1个板子。

2.当然我们也可以用更简单的方法。如果是L≤b₁<……<bₖ≤R,这样的方案数很好求,直接C(R-L+1, k)即可。我们此处使用映射,让b₁=a₁,b₂=a₂+1,……,bₖ=aₖ+k-1。这样映射后,bₖ就不一定≤R了,而是L≤b₁<……<bₖ≤R+k-1。则直接得到方案数为C(R-L+k, k)。这里为什么增量是0,1,2……呢?因为如果增量是2或以上,用原来的公式则可能会出现漏算的现象。例如序列1,2,3。增量为1的时候,有以下变化。

(1,1) → (1,2)

(1,2) → (1,3)

(1,3) → (1,4)

(2,2) → (2,3)

(2,3) → (2,4)

(3,3) → (3,4)

而增量为3时,会有以下变化。

(1,1) → (1,4)

(1,2) → (1,5)

(1,3) → (1,6)

(2,2) → (2,5)

(2,3) → (2,6)

(3,3) → (3,6)

此时我们可以看到,(1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5), (4,6), (5,6)在这里是没有的。如果我们依旧去用那个公式去计算就会出错。简而言之,映射为0,1,2……是为了方便用公式计算。

3.接下来,因为k很大,但是我们是要枚举k的。所以我们使用以下公式,设R-L为m。∑(k=1→N)C(R-L+k, k)=∑(k=1→N)C(m+k, k)=C(m+1, 1)+……+C(m+n, n)=C(m+1, m)+……+C(m+n, m)=C(m+1, m+1)+C(m+1, m)+……+C(m+n, m)-C(m+1, m+1)=C(m+n+1, m+1)-1

所以最终答案就是C(R-L+n-1, R-L+1)-1。我们可以用Lucas定理来做。具体见59题。

代码(c++):

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int p = 1000003;

int qmi(int a, int k)

{

int res = 1;

while (k)

{

if (k & 1) res = (LL)res * a % p;

a = (LL)a * a % p;

k >>= 1;

}

return res;

}

int C(int a, int b) //组合数的计算

{

if (a < b) return 0;

int down = 1, up = 1;

for (int i = a, j = 1; j <= b; i --, j ++ )

{

up = (LL)up * i % p;

down = (LL)down * j % p;

}

return (LL)up * qmi(down, p - 2) % p; //除down等于乘down的逆元,此处为费马小定理,因为p是质数

}

int Lucas(int a, int b)

{

if (a < p && b < p) return C(a, b);

return (LL)Lucas(a / p, b / p) * C(a % p, b % p) % p;

}

int main()

{

int T;

cin >> T;

while (T -- )

{

int n, l, r;

cin >> n >> l >> r;

cout << (Lucas(r - l + n + 1, r - l + 1) + p - 1) % p << endl;

}

return 0;

}


302.网格

题目:

某城市的街道呈网格状,左下角坐标为A(0,0),右上角坐标为B(n, m),其中n≥m。

现在从A(0, 0)点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点(x, y)都要满足x≤y,请问在这些前提下,到达B(n, m)有多少种走法。

输入格式

仅有一行,包含两个整数n和m,表示城市街区的规模。

输出格式

输出一个整数,表示不同的方案总数。

数据范围

1≤m≤n≤5000

输入样例

6 6

输出样例

132

思路:

1.本题就是对卡特兰数的推导。我们可以走绿色的线y=x,不能走到红线。我们要求(0, 0)走到(n, n)的不经过红线的方案数。首先从(0, 0)走到(n, n)共有C(2n, n)种方法(共2n步,选择其中步向上走)。


如图,我们每一个经过红线上的方案都可以从第一次与红线相交的点开始之后的所有线根据红线做轴对称,那么一定可以得到一条从(0, 0)到(m-1, n+1)的路径。所以总方案数为C(2n, n)-C(2n, n-1)=C(2n, n)/(n+1)。本题是(n, m),同理,根据推导,(n, m)关于红线对称的点坐标为(m-1, n+1)。方案数为C(m+n, n)-C(m+n, n+1)。因为本题数据范围非常大,所以我们在算组合数的时候先把分子分母分解质因数,再去做运算。

代码(c++):

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 100010;

int primes[N], cnt;

bool st[N];

int a[N], b[N];

void init(int n)

{

for (int i = 2; i <= n; i ++ )

{

if (!st[i]) primes[cnt ++ ] = i;

for (int j = 0; primes[j] * i <= n; j ++ )

{

st[primes[j] * i] = true;

if (i % primes[j] == 0) break;

}

}

}

int get(int n, int p) //n!里因子p的个数

{

int s = 0;

while (n) s += n / p, n /= p;

return s;

}

void mul(int r[], int &len, int x)

{

int t = 0;

for (int i = 0; i < len; i ++ )

{

t += r[i] * x;

r[i] = t % 10;

t /= 10;

}

while (t)

{

r[len ++ ] = t % 10;

t /= 10;

}

}

void sub(int a[], int al, int b[], int bl)

{

for (int i = 0, t = 0; i < al; i ++ )

{

a[i] -= t + b[i];

if (a[i] < 0) a[i] += 10, t = 1;

else t = 0;

}

}

int C(int x, int y, int r[N])

{

int len = 1; //长度

r[0] = 1;

for (int i = 0; i < cnt; i ++ )

{

int p = primes[i];

int s = get(x, p) - get(y, p) - get(x - y, p); //分子里p的个数减去分母里p的个数

while (s -- ) mul(r, len, p);

}

return len;

}

int main()

{

init(N - 1);

int n, m;

cin >> n >> m;

int al = C(n + m, m, a);

int bl = C(n + m, n + 1, b);

sub(a, al, b, bl); //高精度减法

int k = al - 1;

while (!a[k] && k > 0) k -- ;

while (k >= 0) printf("%d", a[k -- ]);

return 0;

}

6
0
看帖是喜欢,评论才是真爱:
0 / 1000
  • 全部评论
  • 只看楼主
排序:最早
1
0
6
扫码下载
米游社App