BZOJ3456 | 有标号无向连通图计数

这玩意可以搞出生成函数然后大力卷积。。直接设 f(n) 为答案,设 g(n)n 个点有标号无向图个数

\text{ans mod 1004535809 }\gets \text{这玩意是个质数, 原根是 3 } \text{ans}=f\left( n \right) g\left( n \right) =2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)} \text{枚举 1 所在的连通块大小} g\left( n \right) =\sum_{i=1}^n{f\left( i \right) \left( \begin{array}{c} n-1 \\ i-1 \end{array} \right) g\left( n-i \right)} 2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}=\sum_{i=1}^n{\frac{f\left( i \right) 2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}\cdot \left( n-1 \right) !}{\left( n-i \right) !\left( i-1 \right) !}} \frac{2^{\left( \begin{array}{c} n \\ 2 \end{array} \right)}}{\left( n-1 \right) !}=\sum_{i=1}^n{\frac{f\left( i \right)}{\left( i-1 \right) !}\frac{2^{\left( \begin{array}{c} n-i \\ 2 \end{array} \right)}}{\left( n-i \right) !}} \text{生成函数 }F\left( x \right) ,G\left( x \right) ,H\left( x \right) H\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{\left( i-1 \right) !}x^i} F\left( x \right) =\sum_{i=0}^{\infty}{\frac{f\left( i \right)}{\left( i-1 \right) !}x^i} G\left( x \right) =\sum_{i=0}^{\infty}{\frac{2^{\left( \begin{array}{c} i \\ 2 \end{array} \right)}}{i!}x^i} \therefore H\left( x \right) =F\left( x \right) \ast G\left( x \right) F\left( x \right) =H\left( x \right) G^{-1}\left( x \right) \,\,\left( \text{mod }x^{n+1} \right)

BZOJ2796 | POI2012 Fibonacci Representation

网上没什么正经题解。这篇是我从 POI 小书上扒下来译成英文的。用的 Google Trans + 人眼修正,可能有很多语法语义错误。

中间中文的部分是 alphaGem 大大的脑译。超级感谢他。


Problem Description

The Fibonacci number sequence is a sequence of integers defined recursively in the following way :

F_0=0 \,\, F_1=1 \,\, F_n=F_{n-1}+F_{n-2}

The initial elements of this string are : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\cdots

Byteasar investigates how different numbers can be represented as sums or differences of Fibonacci numbers. Currently, he is wondering how to find the smallest term of Fibonacci numbers (not necessarily different) as the sum or difference of these numbers is a given positive integer k . For example, numbers 10, 19, 17 and 1070 can be represented minimally, respectively, by means of 2,2, 3 and 4 Fibonacci numbers :

10 = 5 + 5 19 = 21 - 2 17 = 13 + 5 - 1 1070 = 987 + 89 - 5 - 1

Help Byteasar! Write a program which for a given positive integer k determines the minimum number of Fibonacci numbers needed to represent the number k as their sum or difference.

The number of queries p \leqslant 10 , and for every p the given intager k \leqslant 4 \times 10^{17}.


Solution

Introduction

A positive integer k is given . The number k is represented by a pair of multiset ( P_+ , P_- ) satisfying the condition:

\sum_{i \in P_+}{F_i} - \sum_{j \in P_-}{F_j} = k

The size of the representation will be the sum of the sizes of multiset P_+ and P_- . We will call one representation optimal if there is no other representation of the number k with a smaller size.

First step

Intuitive observation. First of all, we can accept without losing generality that all elements in P_+ and P_- multiset (or indexes of Fibonacci numbers in the representation) are not less than 2 . Next:

Observation 1. If there is an index i in the representation of Fibonacci numbers, such that i \in P_+ and i \in P_- , this representation is not optimal.

Obviously the representation described above can be improved by removing one occurrence of the index i from both multisets.

Although the terms of the task allow the use of one Fibonacci number more than once, it seems natural (GNAQ: well, is it really natural???) that in this way no optimal representation will be obtained. An example from the content of the task (10 = 5 + 5) seems to contradict it, because we can also represent the same number differently, this time without repetition: 10 = 8 + 2 .

Observation 2.  A representation in which any Fibonacci number occurs at least three times is not optimal. What’s more, there is an optimal representation for k in which every Fibonacci number occurs at most once.

Proof. To justify the above, simple bills based on the definition of the recurrent Fibonacci sequence are sufficient:

(1)\,\, 3F_i = F_{i-2} + (F_{i-1} + F_i ) + F_i =F_{i-2} + (F_{i+1} + F_i) = F_{i-2} + F_{i+2} (2)\,\, 2F_i = F_{i-2} + (F_{i-1} + F_i) = F_{i-2} + F{i+1}

By means of operation (1) each triple occurrence of the Fibonacci number can be replaced by the appearance of only two Fibonacci numbers, which of course reduces the size of representation. Such an operation can not, therefore, be feasible in any optimal representation. However, by means of operation (2), we can gradually eliminate all double occurrences of Fibonacci numbers from the representation, without diminishing the size of the representation. However, you should be more careful here, because after performing the operation (2) , the numbers F_{i-2} and F_{i+1} can occur in the representation many times, so we could potentially get an infinite sequence of deleting double occurrences. It is worth noting, however, that each such operation reduces the sum of the Fibonacci number indices present in the representation by one. This allows you to make sure that the second type of operation will always be done only finitely times and finally each Fibonacci number will occur in the representation at most once. (For example, if after performing an operation, the number of F_2 occurs twice, we can change its occurrences to F_3 and state that the representation was not optimal. )

From the previous considerations, it appears that we can focus on searching for sets (but not multisets) of P_+ and P_-, in which we use one Fibonacci number no more than once. In the further part of the description, we will only be interested in such representations.

What’s more, it is not difficult to find out that in the optimal representation of numbers, it is not worth using the Fibonacci numbers that are significantly larger than the number k. This statement is specified in the following observation. We omit the proof of observation – it will result in proof of correctness of the standard solution.

Observation 3. If F_m \leqslant k < F_{m+1} , then there is an optimal representation of the number k , in which the indexes of Fibonacci numbers do not exceed m + 1 .

Observation 4.  Let (P_+, P_-) be a representation of the number k . If for certain i it occurs:

(a)\,\, i \in P_+ \text{ and } i+1 \in P_+ \text{ or} (b)\,\, i \in P_= \text{ and } i+1 \in P_- \text{ or} (c)\,\, i \in P_- \text{ and } i+1 \in P_+ \text{ or} (d)\,\, i \in P_- \text{ and } i+2 \in P_+

then this representation (P_+, P_-) is not optimal.

Theorem 1.F_m \leqslant k \lt F_{m+1},那么最优分解要么满足 m\in P_+,要么满足 m+1\in P_+

Proof. 如果 k \leqslant 2,命题显然成立。假设对于一个 k\geqslant 3,命题不成立。我们取出 k 的任意一种最优分解 (P_+,P_-),并且设 z=\max P_+。根据假设,我们有 z\ne m \land z\ne m+1

​ 首先,我们假设 z\leqslant m-1。根据 Observation 4 的 (a) 一条,我们可以得到的最大的 k 值是

F_{m-1}+F_{m-3}+F_{m-5}+\cdots

​ 显然地,这一串的和小于 F_m。(考虑归纳法证明。)我们又有 F_m\leqslant k,这种情况不可能。

z\leqslant m-1 的情况被排除了。那么反过来,假设 z\geqslant m+2。同样根据 Observation 4 的 (b)\, (c)\, (d) 三条,我们可以得到的最小的 k 值是

F_{m+2}-F_{m-1}-F_{m-3}-F_{m-5}-\cdots>F_{m+1}

​ 然而,k\lt F_{m+1}。所以这种情况也不成立。命题得证。

这个定理大大减少了我们要讨论的情况。但是不止如此。考虑到 F_m\leqslant k \lt F_{m+1},我们可以得出 k-Fib_mF_{m+1}-k 都不超过 F_{m-1}(因为 F_{m+1}-F_m=F_{m-1})。

情况立即被大幅减少了。这也用另一种方式得出了 Observation 3 的结论(而且比它更强)。那么我们就得到了一种 O(2^{\frac{m}{2}}) 的做法:每一步枚举从 F_{m}F_{m+1} 中选择哪一个。

Theorem 2. Assume that F_m \leqslant k < F_{m+1} . If k - F_m \leqslant F_{m+1} -k, then there is an optimal representation in which m \in P_+ .

Proof. In the proof, it is enough to limit to the case when k \geqslant 3 . Let us mark a = k - F_m , b = F_{m+1} - k. Note that if in the representation of the number k we use the component F_m , then it will leave us the number a , and if we use F_{m + 1} , it will leave us b (or -b , but this is basically the same thing). It should therefore be shown that in the case where a<b , the number of components in the optimal representation of the number a is not greater than the number of components necessary to represent the number b. Note that a + b = F{m-1} . Consider two cases:

a <F_{m-3}, then b>F_{m-2}. By Theorem 1, we should use the F_{m-1} or F_{m-2} component to try to break down the number b. In the first of these cases, we remain with the number a to decompose (using two components, which is unprofitable, because the same situation could happen in one move). If we use the F_{m-2} component, we will have to continue to represent the number b-F_{m-2}, however, note that b-F_{m-2} = F{m-1}-a-F_{m-2} = F_{m-3}-a, we would have such a move also with a. In both cases, it is not worth splitting the number of b.
a \geqslant F_{m-3} , then F_{m-3} \leqslant a \leqslant b \leqslant F_{m-2}. Based on Theorem 1, we have two options to consider: the next component of the representation (both cases where we try to further decompose a and b) can be either F_{m-3} or F_{m-2}. However, a-F_{m-3} = F_{m-2}-b and F_{m-2}-a = b-F_{m-3}. Hence, with both a and b we have the same possibilities for further decomposition.

The final conclusion is as follows: the representation of the number a will always require no more operations than the representation of b. Thus it is safe to add m to the P_+ set and optimally represent what is left.

Theorem 3. Let us assume that F_m \leqslant k < F_{m + 1}. If k - F_m> F_{m + 1} - k , then there is an optimal representation in which m + 1 \in P_+ .

Proof. Analogous to the proof of theorem 2.

The last two propositions suggest for each k the greedy movement to be made. If before this movement occurs F_m \leqslant k < F_{m + 1} (and, let’s say, m> 4) occurs, then the remaining k' after the movement does not exceed \max (k - F_m, F_{m + 1} - k ), that is:

k' \leqslant \frac{F_{m+1}-F_m}{2}=\frac{F_{m-1}}{2}=\frac{F_{m-2}+F{m-3}}{2}<\frac{2F_{m-2}}{2}=F_{m-2}

This shows that after roughly \frac{m}{3} of the movements we get a full representation of the number k. Depending on how effectively we implement single movement, we will get a solution with time complexity O(m^2) = O(\log^2k) or O(m) = O(\log k). Each of these solutions, of course, achieves the maximal point.

关于原根判定的若干证明

其实这个证法是从 zhx 的讲稿中看+结合我自己 yy 出来的……其实这个做法的来源是拉格朗日定理,改天学了之后说不定我会有什么新的认识……

引理1 \,\,\,\, 如果 G = <a> ,称 G 为循环群,若 G 为有限循环群,可知当 |G| = \infty 时, G 与整数加群 \mathbb{Z} 同构,当 |G| \ne \infty 时, ord(a)=|G|

设在质数 \text{mod } p 意义下进行加法和乘法, 那么乘法群 G=\{1,2, \cdots ,p-1 \} 是一个循环群。设 aG 的生成元 (<a>=G),易知 ord(a) = |G| = \varphi(p)

引理2 \,\,\,\, 由欧拉定理可知 \forall a \in G \,,\,ord(a)|\varphi(p)

引理3 \,\,\,\,k=ord(a) \,\,\,(a \in G) ,则 a^k=e , a^{k+i}=a^i

引理4 \,\,\,\, 设原根为 a ,对于\forall 1\leqslant i \leqslant p-1 , \exists x >0 \text{ s.t. } a^x=i \,\, (\text{ mod } p)

引理5 \,\,\,\, 设原根为 a , 仅有 a^{t\varphi(p)}=e ,其中 t \in \mathbb{N}_+

原根判断:a 为原根的充要条件是:对于所有 p 的质因子 d ,都有 a^{\frac{\varphi(p)}{d}} \ne 1

证明:

ord(a)=k

k=\varphi(p) ,则 a 是循环群的生成元,可知 a 为原根,并且 a^{\frac{\varphi(p)}{d}} \ne 1

k < \varphi(p) 时,据引理 2 可知 ord(a)| \varphi(p)

t = \frac{\varphi(p)}{k} , 显然 t>1

dt 任一质因子,显然有 \frac{\varphi(p)}{t}|\frac{\varphi(p)}{d} ,据引理 3 可知 a^{\frac{\varphi(p)}{d}}=1 ,由引理 4 可知 a 显然不是一个原根。

于是胡言乱语地证明完了。

[HNOI2008] Cards

这应该是最传(麻)统(烦)的做法

首先题目里面有句话说

输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

这话啥意思?意思就是置换群大小 |G| = m+1 (自己到自己也算一个)

(并且(除幺元置换之外)没有不动点,这个性质直接导致了那个组合数的解法)

上文的大概证明可以找找洛谷上的题解

不过我们还是可以这么做:

找每个置换 g_i 的循环节,然后DP出不动点的个数。

最后算一下方案就好了, 直接硬上 Burnside

 

从小学开始的数数

Introduction

\sigma 是一个从集合 \mathbb{A}=\{ 1,2,\cdots,n \} 到自身的一一映射 , 那么可以称 \sigma 为置换 ,  形如

\sigma =\left( \begin{matrix} 1& 2& 3& \cdots& n \\ a_1& a_2& a_3& \cdots& a_n \end{matrix} \right)

(其中 \{a_i\} 是一个排列)

P.S. 置换可以做乘法,比如 \left( \begin{array}{c} a \\ b \end{array} \right) \cdot \left( \begin{array}{c} b \\ c \end{array} \right) =\left( \begin{array}{c} a \\ c \end{array} \right)

置换+群论

置换群 ?

置换群 (G,\cdot) (我就直接记作 G 了…) 是一个置换的群. 也即一个带有 (其实严格说叫做装备 equip) 二元运算的置换的集合 , 并满足群的四个性质:

  1. \text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G
  2. \text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)
  3. \text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a
  4. \text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e

(所有的群存在唯一逆元和唯一幺元 , 具体的证明在一个叫做 “OI实用群论” 的文里)

染色问题与等价

定义 在一个群上 , x 为对集合 \mathbb{A} 元素的着色方案 , \mathbb{C} 为所有着色方案的集合 ;

定义 如果 \exists g_i \in G 使得 g_i \cdot x = y , 称作 x,y 等价.

Burnside Lemma

要解决的问题就是在给定置换群 G 和着色方案集合 \mathbb{C} 的情况下, 求出有多少种本质不同的着色方案 (也就是两两不等价).

定义 \mathbb{C}(f) 为在置换 g_i \in G 的作用下不变的染色方案的集合. 集合中的元素(这里的元素是染色方案)又称该置换下的不动点.

N(G,\mathbb{A})= \frac{1}{|G|}\sum_{ g \in G } |\mathbb{C}(g)|

(等价类数目为各集合不动点数目的均值)

Pólya Theorem

G 为对 n 个对象的置换群 , 每个对象可以用 m 种颜色染色 , 等价类数目是 :

N(G,\mathbb{C}) = \frac{1}{|G|} \sum_{ i = 1 }^{|G|} m^{c(g_i)}

其中 c(g_i) g_i \in G 的轮换 (循环节) 的个数 .

(说到轮换 , 突然想到曾经写过一个挺好玩的文)

这就意味着如果染色 x \in \mathbb{C} g_i \in G 的作用下不变 , 那么每个轮换中的元素必须染同种颜色 .

Important conclusions

第一个结论是循环移位的。

通过(循环)移位形成的置换,假设一个 n 个对象的置换,循环移位 k 位,轮换数为 \gcd(n,k)

第二个结论是图上置换群的。

对于 n 个点的无向有色完全图,点的置换有 n 个元素,对于每一个大小设为 a 的轮换,这个轮换对应的完全子图的边的轮换 \frac{a}{2} 个,对于两个大小为 a,b   的轮换,ab 之间的边所形成的置换,它的轮换有 \gcd(a,b) 个。

证明的话 我们先证后面那条,考虑一条边的颜色 c(x,y) 其中 xy 属于不同的轮换 ( 轮换大小分别为 n,m ) ,考虑边的轮换都要同色,这样我们保证的是 \forall k , c(x,y) = c(x+k \mathrm{ mod } n , y+k \mathrm { mod } m)

那么每个点其实都一样了。用类似结论 [1] 的证法可以发现是 \gcd(n,m)

而且你会发现因为一共 ab 条边,所以说每个循环节大小是 \mathrm{lcm}(n,m) 的。

然后前面那条是类似的。。(不负责任)

前面那条的话,一个  好理解的证法是枚举一个点,发现这个点所在的对称轴把轮换这个环分成两半了。然后对于对称的一半,这些点与 1 的边会转会来,然后只需要考虑一半的点就好了-0-

– END –

exgcd 合并同余方程组

\begin{cases} x\equiv a_1\ \left( \text{mod\ }p_1 \right) \\ x\equiv a_2\ \left( \text{mod\ }p_2 \right) \\ x\equiv a_3\ \left( \text{mod\ }p_3 \right) \end{cases}

以前做 CRT 一直是用那个构造性的暴力式子 ( q_{ji} 表示 p_jp_i 下的逆元 ):

x \equiv \sum_{i=1}^{n}{( a_i \cdot \prod_{j \ne i}{(p_j \cdot q_{ji})} )} \mod {(\prod_{i=1}^{n}{p_i})}  

(不过这个式子无比好记&&好用)

现在我们来考虑用 exgcd 去合并 CRT 方程。

直接先考虑俩方程

x \equiv a_1 \mod p_1

x \equiv a_2 \mod p_2

搞成某种加法形式

x + y_1p_1 = a_1

x + y_2p_2 = a_2

减一下

y_1p_1-y_2p_2=a_1-a_2

我习惯把减号改成加号

y_1p_1+y_2p_2=a_1-a_2

 

直接暴力 exgcd 这个方程,无解的条件是当且仅当 \gcd(p_1,p_2) \nmid (a_1-a_2)

求出解后记得 \mod p_2 ,这相当于合并方程了(注意 CRT 方程组最后的解的模数是 \prod_{i=1}^{n}{p_i} 。)

然后回代出第一个方程的特解 x_1 

x_1 = a_1-y_1p_1

(代码上的一个小技巧:因为这特解和 a_1相等同余的并且我们还要合并其他方程,所以直接更新 a_1

然后我们考虑通解是这玩意 : 

x \equiv x_1 \mod \mathrm{lcm}(a_1,a_2)

所以记得变一下模数。(可以维持那个特解不用变,因为在 \mathrm{lcm} 下是同余的)

大概的(伪)代码:

 

洛谷 P1660 数位平方和

最大的 xS(999999) \,\, (K=6) ,这个数字是 3188646 。其余待求函数值的 x 都小于这个数字。

所以最多是 4 \times 10^6 个元素求函数值然后再求个和,直接暴力。

试一下样例发现会出环,环上答案为环上最小值。

做完了。

 

[CYYZOJ 1020] 校验码加强版

首先每一位独立。

对于每一位,统计不合法答案,即有至少一行/列全 0

先枚举有几列必定全为0 ,然后拿出可能非 0 的列。

然后让这些列上的所有行都满足条件。即每一行至少填一个 1

然后乘容斥系数。

 

[Codeforces R489D2C] Nastya and a Wardrobe

手模一下发现除掉最后一轮会形成一个区间

那么

L=\left( \left( \left( x\times 2 \right) -1 \right) \times 2-1 \right) \times 2-1\cdots =x\cdot 2^k-2^{k-1}-2^{k-2}\cdots -1 L=x\cdot 2^k-2^k+\text{1 } R=x\cdot 2^k \text{ans}=\frac{S\left( L,R \right) \times 2}{2^k} =\frac{\frac{\left( R-L+1 \right) \left( R+L \right)}{2}\times 2}{2^k} =\frac{2^k\cdot \left( x\cdot 2^{k+1}-2^k+1 \right)}{2^k} =x\cdot 2^{k+1}-2^k+1

然后暴算这个东西。