數論&組合例題思路

注：相關引理,方法證明見于數論+組合后面

1.構造一個只由8組成的數，使得它能被k整除并且長度最小

設答案長度為$n$

可得到

$ \frac{8 \times (10^n - 1)}{9} \equiv 0 \pmod k$

即

\[\begin{cases} 8 \times 10^n - 8 \equiv 0 \pmod k\\ 8 \times 10^n - 8 \equiv 0 \pmod 9 \end{cases} \]

$8 \times 10^n \equiv 8 \pmod {9 \times k}$

則 $10^n \equiv 1 \pmod {\frac{9 \times k}{\gcd(8,k)}}$

令 $p = \frac{9 \times k}{\gcd(8,k)}$

則當$\gcd(10,p) = 1$時，有

$10^{\varphi(p)} \equiv 1 \pmod p$

如果有解，則$\gcd(10,p) = 1$,有答案為$\varphi(p)$，但不一定是最小

由引理：最小答案必是$\varphi(n)$的約數

所以$\varphi(p)$的約數$r$中最小的且滿足

$10^r \equiv 1 \pmod p$

才是答案

2.$ax \equiv 1 \pmod b$的最小正整數解

轉化：$ax \equiv 1 \pmod b$ $\to$ $ax = b(-y) + 1 $ $\to$ $ax + by = 1$

由裴蜀定理：$\gcd(a,b) = 1(\gcd(a,b) | 1)$ ------- 1

使用擴展歐幾里得先求特解$(x_0,y_0)$

由1式和通解形式可得通解

$x = x_0 - b \times \frac{k}{\gcd(a,b)} \ (k \in Z)$

找到合適的$k$即可得到最小正整數解

P1516 青蛙的約會

設跳了p次

由題:$x + pm \equiv y + pn \pmod L$

$(m - n)p\equiv y - x \pmod L$

$(m - n)p = L(-k) + (y - x)$

$(m - n)p + Lk = y - x$

即看這個方程是否有解，若有，即求最小整數解

注意：$m - n,y - x$可能是負數

事實上，我們在解

$(m - n)p \equiv y - x\pmod L$

由同乘性可以乘$-1$來變系數

a,b已知，求最小的k,使得$yb \equiv k \pmod a$ 成立且$y$最小

$k = \gcd(a,b)$

求$yb + xa = \gcd(a,b)$的最小正整數解($y$)

P2421 荒島野人

題意即為：求最小模數$M$,使得對

$\forall 1 \leqslant i < j \leqslant n,c_i + p_i \times x \equiv c_j + p_j \times x \pmod M $

$(min(l_i,l_j)) < x $ 無解

$ x(p_i-p_j) \equiv c_j - c_i \pmod M$

$x(p_i - p_j) + My = c_j - c_i$

枚舉$M$

記得給系數除$\gcd$

P2054 洗牌

先枚舉：

1 2 3 4 5 6 7 8

5 1 6 2 7 3 8 4

7 5 3 1 8 6 4 2

8 7 6 5 4 3 2 1

4 8 3 7 2 6 1 5

2 4 6 8 1 3 5 7

2的坐標：$2\to4\to8\to7\to5\to1$

3的坐標：$3\to6\to3\to6\to3\to6$

$\cdots\cdots$

看到前面一部分是在$\times 2$,但后面又變小。結合洗牌規(guī)則，$\times 2$應該仍存在，考慮取模

$8 \times 2 = 16$，$16 \% 9 = 7$

$7 \times 2 = 14$，$14 \% 9 = 5$

$6 \times 2 = 12$，$12 \% 9 = 3$

似乎得到：若起始坐標為$x$,則終點為

$x \times 2 ^ m \% (n + 1)$~~(能過樣例)~~

下證正確性

設目標數的坐標為$x_0$

我們以$\frac{n}{2}$為分界線，很明顯，當一個數在分割線左邊($x_0 \leqslant \frac{n}{2}$)時，洗完牌后他的位置將$\times 2$(分割線右邊$x_0$個數在他前面，前面再有$x_0 - 1$個數，他自己就在$2 \times x_0$處)

接下來考慮在分割線右邊的情況

設$k=x_0 - \frac{n}{2}$，則他前面(到分界線)有$k - 1$個數。

由規(guī)則可得到：下一次的位置會在$2 \times k - 1$($2 \times (k - 1) + 1$)

帶入$k$的定義：$2 \times k - 1 = 2 \times x_0 - n -1 = 2 \times x_0 - (n + 1)$

可見：每洗一次牌，就相當于給原坐標乘以2再減去一個$n + 1$.

由于每次減完后坐標一定在$1-n$之間，所以可以理解為取模

因此得到：$x \times 2 ^ m \% (n + 1)$

好的完成第一步(doge)

$N \leqslant 10^{10}$,硬枚不行

那就求解：$x \times 2 ^ m \equiv L \pmod {n + 1}$

變形1：$x \equiv L \times (2^m)^{-1}\pmod {n + 1}$

變形2：$x \times (2^m \% (n + 1)) \times L ^ {-1} \equiv 1 \pmod {n + 1}$

這時發(fā)現：對于變形2：既不能保證$n+1$為質數，也不能保證$\gcd(L,n+1) = 1$，求逆元的方法均不能使用

而對于變形1，$\gcd(2^m,n+1) = 1$($n+1$為奇數)

可以用擴歐或者歐拉定理

P2158 儀仗隊

可以知道：長和寬的長度互質的矩形有一個頂點能被看到

那就不難了：求$2$到$n - 1$($n$個人邊長最大$n - 1$)的歐拉函數并求和，再$\times2$（長寬可互換）

注意$1\times1$($4$個人)中還能看見三個，要加上

P2303 Longge的問題

求$\sum\limits_{i = 1}^{n} \gcd(i,n)$

$O(n) = 4,294,967,296$,暴力不可行 ~~但能得分~~

若$i$與$n$互質，則$\gcd(i,n) = 1$

如果$i$是$n$的約數字，則$\gcd(i,n) = i$

設$\gcd(i,n) = x$的有$k$個

則

\[\begin{aligned} k &= \sum\limits_{i = 1}^{n}[\gcd(i,n) == x] \\&= \sum\limits_{i|x}[\gcd(\frac{i}{x},\frac{n}{x}) == 1] \end{aligned} \]

因為$1 \leqslant i \leqslant n$,所以$1 \leqslant \frac{i}{x} \leqslant \frac{n}{x}$

令$\frac{i}{x} = t$

則$k = \sum\limits_{t = 1}^{\frac{n}{x}}[\gcd(t,\frac{n}{x}) == 1] = \varphi(\frac{n}{x})$

也就是說對于每個$n$的約數$x$，他對答案的貢獻是
$x \times k = x \times \varphi(\frac{n}{x})$

則答案為：

$\sum\limits_{x | n}x \times \varphi(\frac{n}{x})$（對$1$也適用）

注意1：如果$i$是約數，那$n/i$也是。可以同時處理

注意2:如果遇到平方數，需要判斷$i != n / i$后才能分別處理

P2155 沙拉公主的困惑

求$(\sum\limits_{i = 1}^{N!}[\gcd(i,M!) == 1] )\% R$

設$1 \leqslant p_1,p_2,\cdots p_n \leqslant M!$是滿足與$M!$互質的數($p_1 < p_2 < \cdots < p_n$)，那么個數為$\varphi(M!)$

由引理可知：$\gcd(p_i,M!) = \gcd(p_i + l \times M!,M!)$

也就是說，給每一個$p_i$加一個$M!$,得到的$\varphi(M!)$個數依然與$M!$互質

則

$[1 ,M!]$中有$\varphi(M!)$個數

$[1 + M! ,2 \times M!]$中有$\varphi(M!)$個數

$[1 + 2 \times M! ,3 \times M!]$中有$\varphi(M!)$個數

$\cdots$

$[1 + (r - 1)\times M!,r \times M!]$中有$\varphi(M!)$個數

又$r \times M! \leqslant N!$

則$r \leqslant \frac{N!}{M!}$

即$1 \leqslant r \leqslant \frac{N!}{M!},r \in Z$

所以這樣的區(qū)間一共$\frac{N!}{M!}$個

答案就是

$\varphi(M!) \times \frac{N!}{M!}$

接下來考慮$\varphi(M!)$的求法

嘗試推廣：階乘的歐拉函數求法

用遞推的方法，使用歐拉函數的積性函數性質

如果$\gcd(M,(M - 1)!) = 1$,也就是說$1-(M - 1)$全都不是$M$的因數，那么$M$就是質數

\[\begin{aligned} \varphi(M!) &= \varphi((M - 1)!) \times \varphi(M) \\&= \varphi((M - 1)!) \times (M -1) \end{aligned} \]

否則，$M$就是合數，則$M$的最大質因子一定在$1 - (M - 1)$之間，也就是說$M$的所有質因子全部在$1 - (M - 1)$之間，那么

\[\begin{aligned} \varphi(M!) &= M! \times \prod\limits_{i = 1}^{k}(1 - \frac{1}{p_i}) \\&= M \times (M - 1)! \times \prod\limits_{i = 1}^{k}(1 - \frac{1}{p_i}) \\&= M \times \varphi((M - 1)!) \end{aligned} \]

但新的問題出現了:這樣的遞推是$O(M)$的。

$O(TM)$???（bushi）

啊看錯了$M \leqslant 10^7$數組~~應該也許大概~~開的出來

直接預處理一遍后$O(1)$輸出

$O(M + T)$

哦對了還有取模

首先看到求余后結果可能是0（先放到這里）

$R$是質數,則

$\frac{\varphi(M!) \times N!}{M!} \% R = \varphi(M!) \times N!\times (M!)^{-1} \% R$

$OK$再看怎么判斷結果是$0$

如果$N >= R$，結果一定是0$\cdots\cdots\cdots$嗎

這里又出現一個問題，回到式子

$\varphi(M!) \times \frac{N!}{M!}$

有這樣的可能：$N >= R$,但是$\frac{N!}{M!}$中$N!$的$R$因子全部被$M!$約掉了，即$\frac{N!}{M!}$可能并不是$R$的倍數

又引出一個問題：常用思路下會在分別預處理是直接取模，即對$N!,M!$分別取模，但是上面的可能直接否定了這一做法。

這說明了預處理的時候要避開$\%R == 0$的情形

那么，我們如果發(fā)現當前處理的數字是$R$的倍數，就直接把$R$全除完后再預處理（相當于把$N!,M!$中的$R$提前約掉）

那什么時候一定是0呢

那就是$N!$中的$R$的個數比$M!$中的多

也就是$\lfloor \frac{N}{R}\rfloor > \lfloor \frac{M}{R} \rfloor$

P4139上帝VS集合

略

組合

給定四個正整數 $m$、$n$、$p$ 和 $q$（其中 $p < m$ 且 $q < n$），在坐標系中有四個點$ A(0,0)$、$B(p,0)$、$C(m,q)$ 和 $D(m,n)$ 的情況下，有多少對路徑 $(f, g)$ 滿足路徑 $f $從點 $A$ 出發(fā)到點 $D$，路徑 $g$ 從點 $B$ 出發(fā)到點 $C$，且這兩條路徑不相交。

先畫圖

沒有明顯特征，看看非法路徑

有交點$\cdots$，突然想起之前證明卡特蘭數（詳情見于數論+組合）中的非法路徑

可以等效轉化

直接變成：從$A$到$C$，從$B$到$D$的路徑組合數

那么直接整體$-$非法

$ans = C_{m+n}^{n} \times C_{m - p + q}^{q} - C_{m+q}^{q} \times C_{m-p+n}^{n}$

重點：等效替代法

P3223 排隊

$n$ 名男同學，$m$名女同學和兩名老師排成一條直線，任意兩名女同學不能相鄰，兩名老師也不能相鄰，求排法。（注意：任意兩個人都是不同的）

方法1：先插

男生無要求，排列$A_{n}^{n}$

把老師插入，方案$A_{n+1}^{2}$

插入女生，方案$A_{n+3}^{m}$

注意到這樣的話老師之間必有男生，但也可以沒有

將兩個老師和一個女生打包，方案$A_{2}^{2} \times C_{m}^{1}$

再插入，方案$n+1$

插入剩下的$m-1$個女生：$A_{n+2}^{m-1}$

$ans = A_{n}^{n} \times A_{n + 1}^{2} \times A_{n + 3}^{m} + 2m(n + 1)\times A_{n}^{n} \times A_{n+2}^{m-1}$

方法2：先討論

先排男生和老師

如果排完后老師挨在一起，方案數為$A_{n+1}^{n+1} \times A_{2}^{2}$

此時兩個老師之間插入一個女生，方案$2m$

再將兩個老師和插入的女生看作一個整體，方案$A_{n+1}^{n+1}$

再將剩的女生插進去，方案$A_{n + 2}^{m - 1}$

總數$2mA_{n+1}^{n+1}\times A_{n+2}^{m-1}$

如果老師不相鄰，那么直接插

$(A_{n+2}^{n+2}-A_{n+1}^{n+1}A_{2}^{2})A_{n+3}^{m}$

相加即可

平等的恨著每一道高精

[ABC156E] Roaming

有 $n$ 不同個房間，每個房間有
$1$ 個人。人可以在各個房間中移動（不能原地移動）。所有人一共移動了 $k $次，問最后各個房間人數排列有多少種情況。

手撕樣例：

1 1 1

0 0 3

0 3 0

3 0 0

1 2 0

0 2 1

2 1 0

2 0 1

0 1 2

1 0 2

十種情況

顯然，一次移動可以使一個僅一個人的屋子變成空屋，那么，最多產生幾個空屋呢？

在上面的例子中，$n > k$,所以最多產生$k$個空屋子，但如果$n <= k$，那么只能產生$n - 1$個空屋子（至少一個屋子有人）

對于有$i$個空屋子的情況，那么就有($n - i$)個屋子有人

把$n$個人放入（$n - i$）個屋子，每個屋子至少有一個人

選出空屋子后，有人的屋子同時也出來了，方案$C_{n}^{i}$

然后把$n$個人放入$n - i$個屋子里，隔板法，方案$C_{n - 1}^{n - i - 1}$

$ans = \sum\limits_{i = 1}^{min(k,n - 1)}C_{n}^{i} \times C_{n - 1}^{n - i - 1}$

求$x$的大于$1$的因子組成的滿足任意前一項都能整除后一項的序列的最大長度，以及滿足最大長度的序列的個數。

$x = \prod\limits_{i = 1}^{k}p_i^{\alpha_i}$

則

$len_{max} = \sum\limits_{i = 1}^{k}\alpha_i = l$(后面用)

(每次給前一項乘一個質因子就能得到下一項)

考慮計算個數

首先，選一個質因子作為第一項，方案數為$k$,選完后對應的$\alpha_i$要減$1$

每次乘的時候從未用過的質因子中選

一個首項對應方案：$\frac{A_{l - 1}^{l - 1}}{\prod\limits_{i = 1}^{k}A_{\alpha_i}^{\alpha_i}}$（重排列）

將這$k$次方案的數量累加即可（由于修改的$\alpha_i$不一樣，各方案之間結果可能不同，不能直接用乘法）

求在一個$n\times n$的國際象棋棋盤上放置$k$個車的方式數量，以確保它們之間不互相攻擊

首先有解的前提：$k <= n$（一個占一整行）

先選出$k$行，方案$C_{n}^{k}$

再豎著看，初始有$n$個空列，每次在剩下的空列中選一個放棋子，選$k$次

方案$C_{n}^{1} \times C_{n - 1}^{1} \times \cdots \times C_{n - (k - 1)}^{1} = \prod\limits_{i = 0}^{k - 1}C_{n - i}^{1}$

相乘即可

P6191 [USACO09FEB] Bulls And Cows S

有$n$只牛，這些牛可以是公牛，也可以是母牛。牛們要站成一排，任意兩只公牛之間至少要有$k$只母牛。
請計算一共有多少種排隊的方法

首先，放一頭公牛，則左右$k$個位置只能放母牛。

為了避免重復，我們默認第$i+1$頭牛只能在第$i$頭牛右邊

這樣，新放一個牛時只能從原來的位置$-k$中選（由于只在右邊放，那么左邊的$k$不考慮，所以只減一個$k$）

不放：$1$

放一個：$C_{n}^{1}$

放兩個：$C_{n - k}^{2}$

$\cdots$

最多放：$\lfloor\frac{n}{k + 1}\rfloor$

\[ans = \sum\limits_{i = 0}^{\lfloor\frac{n}{k + 1}\rfloor}C_{n - k \times (i - 1)}^{i} \]

P3228 [HNOI2013] 數列

長度為$k$的序列，滿足：最后一項不超過$n$,每一項比前一項高出的值不超過$m$,其中$m(k - 1) < n$,求合法序列數

可以看到不確定因素非常多

索性拋開元素本身，直接考慮加法序列(日增長構成的序列)$\{d_i\}$

也就是差分數組（長度$k - 1$）

不考慮其他，有$m^{k - 1}$種加法序列

確定了加法序列，那么首項也會有一個范圍

即$1 \leqslant a_1 \leqslant n - \sum\limits_{i = 1}^{k - 1}d_i(d_i \in [1,m])$

也就是說，一個加法序列對答案的貢獻是$n - \sum\limits_{i = 1}^{k - 1}d_i$

接下來就是求這$m^{k - 1}$個貢獻的和

首先提出來一個$n \times m^{k - 1}$，接下來看減掉了多少

對于$d_1$，$d_1 = 1$的情況是其他$d_i$把$1\sim m$取遍，為$m^{k - 2}$

$d_1 \in [1,m]$

則$d_1$的貢獻為

$1 \times m^{k - 2} + 2 \times m ^{k - 2} + \cdots + m \times m ^{k - 2} $

即$\frac{m(m + 1)}{2} \times m^{k - 2}$

又一共$k - 1$個$d$

所以減掉的就是$(k - 1) \times \frac{m(m + 1)}{2} \times m^{k - 2}$

$ans = n \times m ^{k - 1} - (k - 1) \times \frac{m(m + 1)}{2} \times m^{k - 2}$

P2606 [ZJOI2010] 排列計數

求$1 \sim n$的排列數$\{p_i\}$，滿足

\[\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor} \]

一眼二叉樹結構，每個葉子比父親要大（更專業(yè)的說法是堆）

設$f[i]$表示$1 \sim i$的方案數

樹形結構是確定的，點的編號就那樣，也必須那樣（本人一開始沒意識到這一點，亂分左右子樹）

對于$i$個點

根節(jié)點是固定的（序列中最大值）

接下來就是分成左右子樹來排

問題來了：如何得知對于$i$個節(jié)點，有多少在左子樹，有多少在右子樹？

對于標號為$k$的節(jié)點，它肯定在一個區(qū)間：$[2^p,2^{p+1}]$

那就看看在中點左邊還是在中點右邊，就可以得知是在哪個子樹

e.g:$5 \in [2^2,2^3]$

$5 < (2^2+2^3) / 2 = 6$，在左子樹

$1-i$遞推下來，設左子樹大小為$l$，右子樹大小為$r$，那么

\[f[i] = C_{i - 1}^{l} \times f[l] \times f[r] \]

一個有$n$個元素的集合有$2^n$個不同子集（包含空集），現在要在這$2^n$個集合中取出若干集合（至少一個），使得它們的交集的元素個數為$k$，求取法的方案數，答案模$10^9 + 7$

首先確定交集中的數，方案$C_{n}^{k}$

在含有選定的$k$個元素的情況下，把剩下的元素進行分配，方案$2^{n - k}$，也就是說含有選定的$k$個元素的子集數是$2^{n - k}$

在這些集合里選，很顯然交集中一定有選定的$k$個元素，方案$C_{n}^{k} \times (2^{2^{n - k}} - 1)$（不能一個都不選）

但是更顯然交集中可能還會有其他元素，所以這個答案范圍過大，求的是交集至少為$k$
的方案數

設當前交集的元素個數是$s$,則$k \le s \le n$

舉個例子：當$s = 2$時，會把$s = 3,s = 4,s = 5$均算入答案

那么算了幾次呢

比如說，對于$s = 3$的情況，假設數字為$1,2,3$，那么在$s = 2$中：

選定的數字是$1,2$時，會把$1,2,3$算入（因為至少兩個，所以再配一個就成了$s = 3$的情況）

選定的數字是$2,3$時，會把$1,2,3$算入

選定的數字是$1,3$時，會把$1,2,3$算入

可以發(fā)現：對于$s = 3$，它在$s = 2$中被重復算了$C_{3}^{2}$次

也就是說，對于$s = l$的情況，它在至少為$k$的答案中被計算了$C_{l}^{k}$次

那么為了減去，就要給至少為$3$的答案乘一個$C_{3}^{2}$來匹配，符號為負

但又會影響$s = 4 \cdots$

容斥原理唄

$s = 2$中$s = 4$重復次數：$C_{4}^{2}$

$s = 3$中重復并算上乘的系數：$C_{4}^{3} \times C_{3}^{2}$

很顯然$s = 3$的數大一些，則$s = 4$的符號為正（補足）

那系數呢

易知：$C_{n}^{m} \times C_{m}^{k} = C_{n}^{k} \times C_{n - k}^{n - m}$

代入化簡：系數為$C_{4}^{3} \times C_3^2 - C_{4}^{2} = C_{4}^{2}$

類比可得$s = 5$系數為$C_{5}^{2}$，符號為負

從例子中可以得到答案：

對于至少為$s$次的答案，它的系數是$C_{s}^{k}$，符號為$(-1)^{s - k}$

\[ans = \sum\limits_{i = k}^{n}(-1)^{i - k}C_i^k \times C_{n}^{i} \times (2^{2^{n - i}} - 1) \]

給定$N$,$L$和$R$，統(tǒng)計長度在$1 \sim N$之間，元素大小都在 $L$ 到 $R$ 之間的單調不降序列的數量。輸出答案對$10^6+3$取模的結果。

設長度為$i$時答案為$f(i)$

則

\[ans = \sum\limits_{i = 1}^{n}f(i) \]

~~（廢話）~~

考慮求$f(i)$

可選的數字數$s = R - L + 1$

對于每一個可選的數，可以選擇$a_j$個（$a_j \geqslant 0$）

那么

\[\sum\limits_{j = 1}^{s}a_j = i \]

對于每一種選法，總能排出唯一的序列，選法不同，序列不同，所以沒有重復情況

經典隔板法:把$i$分成$s$堆，允許堆空

\[ans = \sum\limits_{i = 1}^{n} C_{i + s - 1}^{s - 1},s = R - L + 1 \]

由

\[C_{n}^{m} = C_{n - 1}^{m} + C_{n - 1}^{m - 1} \]

展開化簡

\[\begin{aligned} ans &= \sum\limits_{i = 1}^{n} C_{i + s - 1}^{i} \\&= C_{s}^{1} + C_{s + 1}^{2} + \cdots + C_{s + n - 1}^{n} \\&= C_{s}^{0} + C_{s}^{1} + C_{s + 1}^{2} + \cdots + C_{s + n - 1}^{n} - C_{s}^{0} \\&= C_{s + 1}^{1} + C_{s + 1}^{2} + C_{s + 2}^{3} + \cdots + C_{s + n - 1}^{n} - 1 \\&= C_{s + 2}^{2} + \cdots + C_{s + n - 1}^{n} - 1 \\&= \cdots \\&= C_{s + n}^n - 1 \end{aligned} \]

P1450 [HAOI2008] 硬幣購物

共有 $4$ 種硬幣。面值分別為 $c_1,c_2,c_3,c_4$。

某人去商店買東西，去了 $n$ 次，對于每次購買，他帶了 $d_i$ 枚 $i$ 種硬幣，想購買 $s$ 的價值的東西。請問每次有多少種付款方法。

~~這個肯定是要用背包噠~~

首先要學會背包求方案數

其實也沒啥，定義$dp[i][j]$表示前$i$個物品裝滿容積為$j$的方案數

方程把求$\max$變成累加就行了

第一眼多重背包

~~然后我才不會說敲完后狂T但還有10分~~

說明要換背包

常見的有$01$背包求方案，完全背包求方案，$01$在此肯定不可取，難以擴展，考慮使用完全背包(無數量限制下的方案數)，然后剔掉非法方案數

非法方案可分為四大集合：第$i$種硬幣超額使用

也就是減去這四個集合的并集

~~wc野生容斥~~

可得：并集大小 = 至少一種超額 $-$ 至少兩種超額（任意兩個集合的交集） $+$ 至少三種超額（任意三個集合的交集） $-$ 至少四種超額（四個集合的交集）

全集：$dp[s]$（$dp[i]$表示價值恰好為$i$的方案數）

如果只有第$i$種硬幣超額了，也就是說至少用了$d_i + 1$個硬幣

那么在這種情況下的方案一定全部不合法，也就是一個$s - c_i \times (d_i + 1)$的背包所代表的方案全部不合法

即一種硬幣超額的方案數為$dp[s - c_i \times (d_i + 1)]$

類似的可得兩種硬幣超額的方案是$dp[i - c_i \times (d_i + 1) - c_j \times (d_j + 1)](i != j)$，此時應當減去

三種的就是減去三個，四種的減去四個。

注意減的前提一定是夠減（不夠減說明該情況不存在）

算出來并集之后，再拿全集一減就行了

~~直接一個硬核枚舉~~

		if(s >= c[0] * (d[0] + 1)) res += dp[s - c[0] * (d[0] + 1)];
		if(s >= c[1] * (d[1] + 1)) res += dp[s - c[1] * (d[1] + 1)];
		if(s >= c[2] * (d[2] + 1)) res += dp[s - c[2] * (d[2] + 1)];
		if(s >= c[3] * (d[3] + 1)) res += dp[s - c[3] * (d[3] + 1)];
		// 1個 
		if(s >= c[0] * (d[0] + 1) + c[1] * (d[1] + 1)) res -= dp[s - c[0] * (d[0] + 1) - c[1] * (d[1] + 1)];
		if(s >= c[0] * (d[0] + 1) + c[2] * (d[2] + 1)) res -= dp[s - c[0] * (d[0] + 1) - c[2] * (d[2] + 1)];
		if(s >= c[0] * (d[0] + 1) + c[3] * (d[3] + 1)) res -= dp[s - c[0] * (d[0] + 1) - c[3] * (d[3] + 1)];
		if(s >= c[1] * (d[1] + 1) + c[2] * (d[2] + 1)) res -= dp[s - c[1] * (d[1] + 1) - c[2] * (d[2] + 1)];
		if(s >= c[1] * (d[1] + 1) + c[3] * (d[3] + 1)) res -= dp[s - c[1] * (d[1] + 1) - c[3] * (d[3] + 1)];
		if(s >= c[2] * (d[2] + 1) + c[3] * (d[3] + 1)) res -= dp[s - c[2] * (d[2] + 1) - c[3] * (d[3] + 1)];
		//2個
		if(s >= c[0] * (d[0] + 1) + c[1] * (d[1] + 1) + c[2] * (d[2] + 1)) res += dp[s - c[0] * (d[0] + 1) - c[1] * (d[1] + 1) - c[2] * (d[2] + 1)];
		if(s >= c[0] * (d[0] + 1) + c[1] * (d[1] + 1) + c[3] * (d[3] + 1)) res += dp[s - c[0] * (d[0] + 1) - c[1] * (d[1] + 1) - c[3] * (d[3] + 1)];
		if(s >= c[0] * (d[0] + 1) + c[2] * (d[2] + 1) + c[3] * (d[3] + 1)) res += dp[s - c[0] * (d[0] + 1) - c[2] * (d[2] + 1) - c[3] * (d[3] + 1)];
		if(s >= c[1] * (d[1] + 1) + c[2] * (d[2] + 1) + c[3] * (d[3] + 1)) res += dp[s - c[1] * (d[1] + 1) - c[2] * (d[2] + 1) - c[3] * (d[3] + 1)];
		//3個 
		if(s >= c[0] * (d[0] + 1) + c[1] * (d[1] + 1) + c[2] * (d[2] + 1) + c[3] * (d[3] + 1)) res -= dp[s - c[0] * (d[0] + 1) - c[1] * (d[1] + 1) - c[2] * (d[2] + 1) - c[3] * (d[3] + 1)];
		//4個*/
		cout << dp[s] - res;//全 - 并

這里有一個小雞俏 ~~（就是讓小雞變美的方法）~~：用四個位來表示當前各集合是否參與交集，比如$1101$表示的是第一個，第二個和第三個集合的交集，范圍即$0001 \sim 1111(1 - 15 (1 << 4 - 1))$

[ABC172E] NEQ

構造長為 $N$ 的整數序列 $A,B$ ，滿足：

$1 \leq A_i,B_i \leq M$
$\forall i\neq j$，$A_i\neq A_j,B_i\neq B_j$
$\forall i$，$A_i\neq B_i$

求合法構造方案數，對 $10^9+7$ 取模。

第2個性質告訴我們序列中沒有重復元素，則勢必要選出$M$個數來造序列。不過$A,B$中所含的元素種類可能不盡相同

看到性質三，好像想到了些什么

不同，從排列時就保證該性質？

方法一：錯排

這個題中影響錯排的重要因素就是$A,B$所含的元素種類

如果相同，無影響

考慮存在僅一個序列包含的元素時的情形

從錯排的遞推式下手

如果第$n$位的元素$A$中有，那么就是錯排

\[D(n) = (n - 1) \times (D(n - 1) + D(n - 2)) \]

如果第$n$位的元素$A$中沒有，則這個元素可以隨意
“匹配”掉$A$中一位，只需對剩余的$i - 1$位錯排

又因為$B$中備選的$A$中沒有的元素一共$M - N$個，所以

\[D(n) = (M - N) \times D(n - 1) \]

二者合并后得到遞推式

或者，總數 - 非法？

方法二：容斥

對于$A$的一個排列，對應的$B$共有$A_{M}^{N}$種排列（包含非法）

將非法情況分為：有$i$位相等，$i \in [1,N]$

如果有$i$位相等，先選出這$i$位來，那么剩下的$n - i$位由$m - i$個元素的排列補上，方案$C_{N}^{i} \times A_{M - i}^{N - i}$

由容斥：

非法總數 = $\sum\limits_{i = 1}^{N}(-1)^{i - 1}C_{N}^{i} \times A_{M - i}^{N - i}$

也就是說對于$A$的一種排列，合法數為$A_{M}^{N} - \sum\limits_{i = 1}^{N}(-1)^{i - 1}C_{N}^{i} \times A_{M - i}^{N - i}$

$A$又一共有$A_{M}^{N}$種排列，二者相乘即可

P2467 地精部落

求長度為$n$，$h_i \in [1,n], \forall i \ne j,h_i \ne h_j$的波動序列數（一個數不是山峰（比兩邊都大）就是山谷（比兩邊都小））

先康康波動序列的性質

交換不相鄰的$i,i + 1$，會生成一個新的波動序列
若$\{h_i\}$是波動序列，則$\{n - h_i\}$也是一個波動序列

波動序列有對稱性

首先數列有兩大類：第一個是峰/谷

如果第一個是山峰，由性質2，倒一下就成第一項為山谷的情況了，所以不妨只考慮一種 ----- ①

設$dp_{i,j}$表示長度為$i$，第一項為$j$
，且第一項是山峰的序列總數

此時子情況就是第二項為山谷，第三項為山峰

再拿性質二倒一下，就變成了第二項為山峰，第三項為山谷的情況，符合$dp$狀態(tài)，而且方案數不變

有兩種方法讓$j$成為山峰：

使用翻轉，翻轉完后$j$后面的山谷是$j - 1$，那么說明翻轉前這里是山峰，高度$i - (j - 1)$，而且是后$i - 1$項的第一項

\[dp[i][j] += dp[i - 1][i - (j - 1)] \]

交換得來，將$j$與第一項交換，此時序列長度已經是$i$，根據交換條件，可知交換的是$j - 1$

\[dp[i][j] += dp[i][j - 1] \]

由①，最后答案要 $\times 2$

\[ans = 2 \times \sum\limits_{i = 1}^{n}dp[n][i] \% p \]

法二：組合

這樣做會有一個難點：如何保證組合選取的時候不會出現重復元素？

有一件事是明確的：最大的數一定是山峰，記為$h_{max}$，所在處記為$j$

如果$h_{max}$在偶數位上，那么奇數位就是山谷，

此時我們將$dp_{i,0/1}$定義為：長度為$i$，開頭為山峰/谷的方案數

那么：最大數前面數列的開頭一定是山谷（$1$是奇數），后面數列的開頭一定是山谷

又因為波動數列只與數的相對大小有關，所以不管選出來啥數字都可以排出來，而且有最大值做分割，因此左右互不影響，所以先給左邊選數，選完后再論方案，是乘法原理

則

\[dp[i][0] += dp[j - 1][0] \times dp[i - (j + 1) + 1][0] \times C_{i - 1}^{j - 1} \]

（$j \in [1,i],j = 2n,n \in N^+$）

類似的可得奇數：

\[dp[i][1] += dp[j - 1][1] \times dp[i - (j + 1) + 1][0] \times C_{i - 1}^{j - 1} \]

（$j \in [1,i],j = 2n + 1,n \in N^+$）

最后

\[ans = dp[n][0] + dp[n][1] \]

P3330 [ZJOI2011] 看電影

藍結論，黑高精

有$K$個座位，現執(zhí)行以下步驟：

從$[1,K]$中等概率選取一個數$L$
若$L$是空位，則坐下，否則$L$ 加一，再判斷是不是空位，以此重復
若第二步沒找到空位，站著

共$N$人，求全班都有座位的概率

分母簡單，$k^n$

考慮分子

由于標號存在諸多不確定性，我們換個入手點：椅子的狀態(tài)

如果合法，那么要么坐滿，要么有空座位

對于坐滿的情況，我們補一個空座位，合并情況

為了統(tǒng)一，給本來就有空座位的情況也加一個空座位

也就是說，現在一共$k + 1$個座位，空座位有$k + 1 - n$個

由于此時考慮的都是合法情況，所以要找到構造方法使得在此方法下怎么選都是合法的

神之一筆就來了：連成環(huán)

不過很顯然，這樣會算進去一些非法方案，所以肯定要加以限制

由于現在是$k + 1$把椅子，有一把椅子是原本不存在的，那么很顯然，這把椅子上只要不坐人，就是合法方案。

也就是說：一個$k + 1$的圓，其中一個座位不坐人的方法數

如果不考慮不能坐人的情況，方案$(k + 1)^{n}$（反正都成環(huán)了，無論怎么選總能找到空位）

接下來砍掉重復的

這個環(huán)有$k + 1$個斷點，可以形成$k + 1$個序列，那么也就是說每$k + 1$種選法只能形成一個環(huán)，所以方案數應為$\frac{(k + 1)^n}{k + 1} = (k + 1)^{n - 1}$

再考慮椅子不坐人的情況

從空椅子里抽一把不就好了

\[ans = \frac{(k + 1)^{n - 1} \times (k + 1 - n)}{k^n} \]

P2480 [SDOI2010] 古代豬文

求

\[g^{\sum\limits_{d | n}C_{n}^w0obha2h00} \operatorname{mod} 999911659 \]

$g$的系數太大了，肯定要取模

使用歐拉定理：

若$gcd(g,999911659) = 1$

則

\[g^{\sum\limits_{d | n}C_{n}^w0obha2h00} \equiv g ^{\sum\limits_{d | n}C_{n}^w0obha2h00 \operatorname{mod} \varphi(999911659)} \pmod {999911659} \]

發(fā)現$999911659$是質數，所以$\varphi(999911659) = 99991658$

接下來交給$exLucas$

再快速冪一下就OK了

然而會T

發(fā)現$999911658$是四個質數的乘積，因此可以直接對這四個質數上普通$Lucas$再拿$CRT$合并

就好了

P2532 [AHOI2012] 樹屋階梯

用$N$個鋼材搭建高度為$N$的階梯，求方案數

考慮卡特蘭數，那么就要和數論+組合中總結的$Catalan$的應用場景來對照

選出分割全集的集合，并且分成的兩個子集大小和一定

考慮用一個鋼材分成上下兩部分

上面階梯的級數是$x$，下面的級數是$y$，則$x + y = N - 1$，共用了$N - 1$個鋼材（上面用$x$個，下面用$y$個），符合條件

而且分成的兩部分是等價的

那么答案就是$H(N - ((N - 1) - (N - 1))) = H(N)$

上高精就行了

P3306 [SDOI2013] 隨機數生成器

已知$p,a,b,X_1,t$

求使得

\[X_i =(a^{i - 1}X_1 + b\sum\limits_{j=0}^{i - 2}a^j) \equiv t \pmod p(i \geqslant 2) \]

成立的最小$i$（可以是$1$，即$X_1 \equiv t \pmod p$）

化簡

\[\begin{aligned} X_i &= a^{i - 1}X_1 + b \times \frac{a^{i - 1 } - 1}{a - 1} \\&= a^{i - 1}X^1 + \frac{ba^{i - 1}}{a - 1} - \frac{b}{a - 1} \\&= a^{i - 1}(X_1 + \frac{b}{a - 1}) - \frac{b}{a - 1} \end{aligned} \]

所以

\[a^{i - 1}(X_1 + \frac{b}{a - 1}) - \frac{b}{a - 1} \equiv t \pmod p \]

\[a^{i - 1}(X_1 + \frac{b}{a - 1}) \equiv t + \frac{b}{a - 1} \pmod p \]

\[a^{i - 1}(X_1 + \frac{b}{a - 1}) \times (X_1 + \frac{b}{a - 1})^{-1} \equiv (t + \frac{b}{a - 1}) \times (X_1 + \frac{b}{a - 1})^{-1} \pmod p \]

\[a^{i - 1} \equiv (t + \frac{b}{a - 1}) \times (X_1 + \frac{b}{a - 1})^{-1} \pmod p \]

其中$\frac{b}{a - 1} = b \times (a- 1) ^ {-1}$，上述的$-1$次方均指逆元

上$BSGS$就行了

然后特判

$a = 0$：$X_i = b$，判斷$b$是否等于$t$
$a = 1$：$X_i = X_1 + b(i - 1)$

\[i - 1 \equiv (t - X_1) \times b^{-1} \pmod p \]

$X_1 == t$：$ans = 1$

[HNOI2009] 有趣的數列

求一個長度為 $2n$ 的數列，滿足：

它是從 $1 \sim 2n$ 共 $2n$ 個整數的一個排列 $\{a_n\}_{n=1}^{2n}$
所有的奇數項滿足 $a_1<a_3< \dots < a_{2n-1}$，所有的偶數項滿足 $a_2<a_4< \dots <a_{2n}$；
任意相鄰的兩項 $a_{2i-1}$ 與 $a_{2i}$ 滿足：$a_{2i-1}<a_{2i}$。

答案對 $p$ 取模。

（$update:2024/1/12/22:32$破$1000$行祭）

~~看樣例知$Catalan$~~

證明：將這$2n$個數按性質三分成$n$組

設$H(n)$表示$1\sim 2n$的方案數

對照情景

選定分割集合：一組數，兩邊一共剩了$n - 1$組，和一定，數量上符合要求

接下來考慮等價性

設選的是第$k$組，那么前面$k - 1$組的方案應該是完全等價于$H(k - 1)$

即使有大的數跑進前面，小的數被擠到后面也不影響，因為相對關系沒有改變，后面更大的數在$1 \sim2(k - 1)$中（前面）還是大數，小的數字在后面$2k + 1 \sim 2n$中還是小數

再結合兩邊集合的大小和事$n - 1$，所以

\[ans = H(n) \]

第二種理解方法：

結合性質可以得知：一個偶數位上的數字一定比他前面所有的數都大（比前面所有偶數大，比前一個奇數大，前一個奇數大于前面所有奇數）

我們現在把$1 - 2n$依次放到奇數或偶數位上，為了維護遞增，顯然每次都靠最左邊放

那么，$2i$處只能放$\geqslant2i$的數

也就是說，前面$1 - (2i-1)$位已經放置完畢（這樣才能輪到$2i$），而$2i-1$是奇數，所以奇數位比偶數位多

再算上第$2i$個，就變成了：

任意一次放置，都滿足在偶數位上的數的數量小于等于在奇數位上的數的數量

拿進出棧一類比：偶數位代表出棧，奇數位代表進棧，發(fā)現

\[ans = H(n) \]

沒說$p$是質數，上$\text{exLucas}$

~~然后你高高興興的發(fā)現exLucas被卡T了~~

~~真TMD是廢物一個又容易T又不好寫~~

~~狗都不寫~~

那就換個方法：$\frac{1}{n + 1}C_{2n}^{n}$

這個一開始沒有考慮是因為不能保證$n + 1$有逆元

那就約分上快速冪

拆開：

\[H(n) = \frac{\prod\limits_{i = n + 2}^{2n}i}{\prod\limits_{i = 1}^{n}i} \]

用歐拉篩預處理出$1 - 2n$內所有質數，把合數都劈成質數（可用倒序循環(huán)），統(tǒng)計下面各個質數有多少，再看上面的有多少，對應的質數個數一減就行了

P1463 [POI2001] [HAOI2007] 反素數

正整數 $x$約數的個數記作 $g(x)$。

如果某個正整數 $x$ 滿足：$\forall 0 \lt i \lt x$，都有 $g(x) \gt g(i)$，則稱 $x$ 為反質數。現試求不超過 $N$ 的最大的反質數

這個題提到了一個有意思的東西：反質數

設$n = \prod\limits_{i = 1}^{k}p_i^{c_i}$是一個反質數，那么$n$一定滿足：

$p_i$是從$2$開始的連續(xù)的質數
$c_i$單調不增

對于第一個，換成不連續(xù)的質數得到$n'$，在不改變次數的同時，很顯然$n' > n$，但是$g(n) = g(n')$，這不符合反質數的定義

對于第二個，如果出現$i < j,c_i < c_j$，將$p_i^{c_i}p_j^{c_j}$換成$p_i^{c_j}p_j^{c_i}$得到$n''$，顯然$n'' > n$（作比即可得），同樣不符合定義

依靠這些性質，我們可以采用搜索的方法來“枚舉”質數的次數，進而得到符合條件的數

給定一個正整數$N$ ,它可以表示為 $N = p^2q$（$p$和 $q$是兩個不同的質數且唯一）。找出$p$和$q$。

~~不想找~~

~~隨表挑一個硬枚得50（枚$q$）~~

~~從小質數的開始枚分解質因數硬搞可過~~

求$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$的正整數解$(x,y)$的個數模$10^9 + 7$的結果

\[\frac{1}{y} = \frac{1}{n!} - \frac{1}{x} = \frac{x-n!}{xn!} \]

\[y = \frac{x-n!}{xn!} \]

\[y = \frac{1 - \frac{n!}{x}}{n!} \]

$To$ $Be$ $Continued \cdots$

~~(持續(xù)連載還不趕快點贊關注收藏）~~

posted @ 2024-02-17 12:32 why?123 閱讀(80) 評論(0) 收藏舉報

刷新頁面返回頂部

蒟蒻之淚