不定方程 and 组合数计算
题目
小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。
输入描述:
- 每个输入包含一个测试用例。
- 每个测试用例的第一行包含一个整数，表示歌单的总长度K( 1<=K<=1000 )。
- 接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B (B<=10)和数量Y(Y<=100)。
- 保证A不等于B。
输出描述:
- 输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。
问题分解
本题即求解不定方程 \(sA+tB=K\)
以及组合数的计算问题
不定方程
- 两边对A取模得: \(tB ≡ K\, mod\,A\)
- 两边对B取模得: \(sA ≡ K \,mod\, B\)
若想直接解这个同余方程组, 需要AB对彼此存在逆, 也就是说AB应互质
若AB不互质, 记\(g=gcd(A,B)\), 则有\(A = a*g\,; \,B = b*g\)
\(sag+tbg = K\)
\((sa+tb)g = K\)
提取公因式后易知当且仅当K是g的倍数时有解, 记\(K = k*g\)
\(sA + tB = K\)
\(sag + tbg = kg\) \(\mathbf{sa + tb = k}\)
两边对a取模有
\(tb ≡ k \, mod\, a\)
\(\mathbf{t ≡ kb^{-1}\, mod\, a}\)
两边对b取模有
\(sa ≡ k \, mod\, b\)
\(\mathbf{s ≡ ka^{-1}\, mod\, b}\)
而后我们知道了s和t出现的规律
可以只利用其中一个
譬如\(s[i]\) 是一个首项\(s[0] ≡ ka^{-1}\, (mod\, b)\) 公比为b的数列
对于每一个s, 一定会满足\(sa+tb=k\)
\(tb=k-sa\)
故直接求出t也是容易的
至于s所在的数列范围
注意到: \(s[i] = s[0]+ib\)
\((s[0]+ib)+tb = k\)
\(tb = k - s[0]a - iab\)
\(0 ≤ tb = k-[ka^{-1}\, (mod\, b)]a - iab\)
\(iab ≤ k-[ka^{-1}\, (mod\, b)]*a\)
\(i ≤ \mathbf{⌊} { k - [ ka^{-1}\, (mod\, b) ]*a } / ab\mathbf{ ⌋ }\) (擦亮眼睛, 看见地板函数没)
而后可以开始编程了, 调用的函数见文末代码本体
1
2
3
4
5
6
7
8
9
10
11
12
13def solve(A,B,K): #sA+tB=K
g=gcd(A,B)
if K%g!=0:
return 0
a=A//g
b=B//g
k=K//g #sa+tb=k
start=(k*modinv(a,b))%b #s=k*a^-1 mod b
cnt=0
for i in range((k-a*start)//(a*b)+1):
s=start+b*i
t=(k-s*a)//b
print(s,'*',A,'+',t,'*',B,'=',K)
嗯, 只用到了s的出现规律, 半部论语可以治天下
能不能再用上另半部呢?
梳理下我们已有的东西:
- \(sa + tb = k\)
- \(t ≡ kb^{-1}\, mod \,a\)
- \(s ≡ ka^{-1}\,mod\,b \)
记 \(t = [ kb^{-1}\,(mod\,a)] + M*a\)
\(s = [ka^{-1}\,(mod\,b)] + N*b\)
一个很自然的想法是把t和s带回原不定方程:
\[ \lbrace [ ka^{-1} (mod\,b)] + Nb \rbrace*a+\lbrace [ kb^{-1} (mod\,a)] + Ma\rbrace*b=k \]
\[[ ka^{-1} (mod\,b)]*a + [ kb^{-1} (mod\,a)]*b +\mathbf{(N+M)}*ab=k\]
\[ \mathbf{(N+M)}*ab = k - [ ka^{-1} (mod\,b)]*a - [ kb^{-1} (mod\,a)]*b \]
易知等式右端是个定值
而等式左端的M和N是由我为所欲为随意掌控的
易知 M+N 为一个定值
所以 t每增加a, s都要随之减少b
由此思路可优化代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def solve(A,B,K): #sA+tB=K
g=gcd(A,B)
if K%g!=0:
return 0
a=A//g
b=B//g
k=K//g #sa+tb=k
start=(k*modinv(a,b))%b #s=k*a<sup>-1</sup> mod b
cnt=0
s=start
t=(k-s*a)//b
for i in range((k-a*start)//(a*b)+1):
print(s,'*',A,'+',t,'*',B,'=',K)
s+=b
t-=a
组合数计算
记组合数为C(M,N), 其中下标在前, 上标在后, 我也不知道谁想出来的这么别扭的方式
而后放大杀器: 组合数恒等式
\(C_{m+1}^{n+1} = C_{m}^{n+1} + C_m^n\)
高中的时候对这个公式一点也不感冒, 觉得并没有实际意义
上了大学: 真香.jpg简证一下:
\(m+1\)个同学里抽\(n+1\)个同学做值日,
钦定小江同学不用做值日, 那么一共有\(C_{m}^{n+1}\)种选择
但是小江同学的决定权也是很重要的, 他想他应该留下了做值日
老师于是钦定他做值日, 裆燃啦, 现在一共有\(C_{m}^{n}\)种选泽
一共就这两种情况, 于是睿智的小江同学推了一下黑框眼镜,在黑板上写下了:
\(C_{m+1}^{n+1} = C_{m}^{n+1} + C_m^n\)
于是嘛, 对于任意一个组合数\(C_m^n\), 都可以通过递归成\(C_{m-1}^{n}+C_{m-1}^{n-1}\)来计算……
递归个头! 矮十厘米.jpg
不打表还有王Fa?
用一个下三角数组来存储 (我知道你懒得实现下三角数组谢谢)
用一个数组的下三角来存储
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
嗯, 杨辉三角, 想不到吧
生成数组然后访存就好了
1
2
3
4
5
6
7def init(N):
comb =[[0]*N]*N
for i in range(N):
comb[i][0] = comb[i][i] = 1
for j in range(i):
comb[i][j] = comb[i-1][j] + comb[i-1][j-1]
return comb
改进思路
我们知道杨辉三角也能如下存储:
> 1 1 1 1 1 1
> 1 2 3 4 5 6
> 1 3 6 10 … …
> 1 4 10 …
> 1 5 …
> 1 6 …
其对应关系是\(C(m,n) = A[m][n] = B[m-n][n]\)
数组B的生成规律: \(B[x][y] = B[x-1][y] + B[x][y-1]\)
卢卡斯定理
用于计算需要对素数p取模, 并且上下标都大于p的组合数
卢卡斯dalao是这么教你做人的:
\(C_{m}^n mod p = C_{m/p}^{n/p} * C_{m mod p}^{ n mod p}\,mod\,p\)
而后\(C_{m/p}^{n/p}\)如果还是很大,则可以继续递归几次再计算
但如果需要计算对合数取模的组合数时, 该怎么办呢?
中国剩余定理了解一下谢谢
附: 代码本体
1 | def init(N,MOD): |
