扩展欧几里得原理 – Tgotp-Blog

1477: 青蛙的约会

根据题意,设调w次,

有(mw + x)%l = (nw + y)%l

即 mw + x - nw -y = lz(z ∈N)

那么有 (n - m)*w  + lz = x - y

接下来套扩欧就搞定了。

c++代码如下:
[crayon-5b50ac351a942[......]

Read more

5027: 数学题

好气啊,ac不掉。。。。

然而要了claris 的ac代码对拍又没有问题。。。

ps:拍了一个小时。。。

对拍代码如下:

claris的ac代码如下:
[crayon-5b50ac351b7546022[......]

Read more

POJ 2154 Color

首先,直接应用polya定理就可以得到ans=(N^gcd(0,N)+N^gcd(1,N)+…+N^gcd(N-1,N))/N,如果直接计算的话,即便应用快速幂,也改变不了循环计算N项和的复杂度。

于是便不得不从gcd的值入手看是否能合并一些项达到化简的目的了。尽管一共有N项,但gcd的值一定[......]

Read more

POJ 2409 Let it Bead

算是我第一道理解的burnside引理题目

题意

c 种颜色的珠子,组成长为 s 的项链,通过旋转或者翻转得到的情况我们算一种,问总共有多少种不同的方案。

 

思路

Polya定理的应用

设 G 是 p 个对象的一个置换群,用 k 种颜色去染这 p 个对象,若一种染色方[......]

Read more

扩展欧几里得原理

好文章推荐:http://blog.csdn.net/lincifer/article/details/49391175#扩展欧几里德算法附证明

求exgcd;

¨

 

求gcd(最大公因数的)随便补一[......]

Read more

BZOJ 1004: [HNOI2008]Cards

姿势太弱,辣鸡取膜降我ac率;

裸的burnside
—-
置换:
1   2   3   4   5
a1 a2 a3 a4 a5
就是把1位置上的数换成a1上的数

置换群:一群置换就是置换群= =;;

循环:
1 2 3 4 5 6 7
7 5 2 4 6 3 1[......]

Read more