[今天我们继续思考14]矩阵也疯狂（天地之灵5月5日收集整理）

[天地之灵]

矩阵也疯狂（天地之灵收集整理）

1、费伯拉契数列：它是符合这样一个性质的数列：除了开头两个数以外，每个数都是之前两个数之和。
比如以0和1开头的费伯拉契序列叫做标准费伯拉契序列，有
i 0 1 2 3 4 5 6 7 8
f(i) 0 1 1 2 3 5 8 13 21
现在，给你f(0)、f(1)、N和M，请你求出f(N)%M的值（即：编号为N的费伯拉契数除以M的余数）这四个数的范围都不超过2的32次方。

2、台阶计数：
也是一个很古老的问题，有一个N层台阶，每次可以走上一阶、跨上两阶、跳上三阶，甚至，更一般一点，可以走上k阶
那么，N层台阶总共有多少种方法可以走上去呢？ 当然，这个数字很大，和之前一题一样，我们只要求出它除以M的余数。
N、M不超过2的32次方，k不超过100。

3、三色项链
我们有红、黄、蓝三种颜色的宝石，要把它串成一个项链。由于扣环两端的存在，类似“红、蓝、黄”组合和“黄、蓝、红”组合（颠倒）和“蓝、黄、红”（旋
转）被认为是不同的项链。
但是项链未来的主人有一些奇怪的要求，这些要求是某些颜色的右侧不能有相邻的某种颜色。（包括扣环所在位置的两旁）
比如红色的右边不能有相邻的蓝色的宝石，那么“红、蓝、黄” 和“蓝、蓝、红”都是不允许的了，但“黄、蓝、红”仍然可以。
所有颜色的宝石都有足够的数量，你可以任意选择而不用担心宝石不足。
那么，组成一个长为N的项链，总共可以组成不同的项链呢？
输入若干限制条件和N，输出方法除以M的余数。N和M不超过2的32次方。

4、砖块
有一个长为N（N为偶数）米，宽度为3米的走廊，要用若干1米*2米的砖块铺满，比如当N=4时，如下是一种可行的铺设方法
1 2 2 6
1 3 3 6
4 4 5 5
那么，给定N，请问总共有多少种方法．当然，求出除以M的余数即可。N和M不超过2的32次方。

5、高斯费伯拉契
这是一道我原创的题目，简单的说，高斯和费伯拉契都是很强很nb的数学家，各自有一个以他们的名字来命名的数列：
高斯数列（也叫等差数列）
费伯拉契数列（见第一题的描述）这里令f(0) = 0, f(1) = 1（即取标准费伯拉契数列）
一般来说，高斯数列指形如G(i) = a*i + b的数列
假设a、b都是整数，请你求出：对于i从1到N，所有f(G(i))的和，除以M的余数。
a、b、N、M 四个数将被给定，都不超过2的32次方。

6、帕斯卡魔纹
和上一题类似，也是我的原创题；相比而言这一题更加复杂一些。
帕斯卡三角形（中国叫杨辉三角），是这样一个三角形：第0行只有一个数，1
从第1行开始，每行的第一个数和最后一个数都是1，其他位置的数为其上方和左上方两个数之和。
如：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
我们还知道，这个三角形里第J行的第i个数为组合数C(J,i)
现在已知帕斯卡魔纹指这个不完全的矩阵中的某些数，其所在位置（见上行的描述）满足：
(J+i)%k = b （即：行号与列号之和除以k的余数等于b， 行号和列号全部从0开始计算。）
希望请你求出，前N行的所有帕斯卡魔纹上面的数之和，除以M的余数。
b小于k，而大于等于0。k大于1而小于10。N、M都不超过2的32次方。

7、来一道转载的题目，让你对矩阵的魅力体会更加深刻
一个小镇里有N个人，每个人有一些朋友（这里朋友未必是双向的，即：允许A把B当作朋友，但B不把A当作朋友）
有一天，小镇里的居民开始做一个游戏：
第一天，所有人都在自己的所有朋友门口各放上一朵花
第二天，门前有奇数朵花的朋友，在自己的朋友门口各放上一朵花
第三天，门前有奇数朵花的朋友，再在自己所有的朋友门口各放上一朵花
这样下去，请问：第M天的时候，有多少个人门前有奇数朵花。

8、再来一题，让你们知道矩阵不仅仅是矩阵，它不是一个人在战斗！
有一种k-电路矩阵，它有k个输入和k个输出，输入和输出都只有两种状态：高电位或低电位，输出和输出布成一个k*k的二极管矩阵，电子二极管的状态可
以通过激光设置，也具有两种状态：通过与不通过。
换言之，每个输出和输入当中的某些相通。如果所有与它连通的输入中存在一个高电位，那么输出为高电位。如果所有与它连通的输入全部为低电位，则输出低电
位。
现在，将N块相通k-电路矩阵一个接一个拼接成一串，每块电路的输入按照顺序连接到下一块电路板上。
现在，给定k个输入源的输入状态，求出最终一块电路板的k个输出的状态。
k不超过100，而N不超过2的32次方。

9、再来两道调剂的题目，这两道和矩阵没有关系，只是为了调剂大家的情绪
这是一套很老的题目：有N盏灯，一开始全部是关着的，首先把所有灯都打开（1的倍数），然后把所有偶数的灯全部关上（2的倍数），然后把所有3的倍数的
灯，开着的关上，观者的开开
以后依次把所有i的倍数的灯状态改变（关着的打开，打开的关上）
一直到最后只改变第N盏灯为止。
现在请问：有多少灯还是打开的。
当然，如果你写个程序来模拟，那就太简单了，所以我们大大加大N的范围：N不超过2的64次方。
这个范围使你的计算机不能模拟整个过程了，所以——思考新的算法吧。

10、第二道调剂的题目：
有2N张牌，编号从1到2N，现在开始洗牌，每次将牌从中间分成两堆，将前一半依次插入偶数位置，后一半依次插入奇数位置
比如N = 3时，一次操作后得到：
1 2 3 4 5 6
4 1 5 2 6 3
接下来继续这个操作，得到
2 4 6 1 3 5
1 2 3 4 5 6
我们会看到3次操作之后，所有的牌回到了原来位置。
现在，请你用一个期望复杂度在O(N)以内的算法，对于给定的N，求出多少次洗牌操作之后，所有的牌都回到了原来的位置。
并且，请尝试证明一下你的复杂度在O(N)以内。

[鋆邓]

第一次发起主题，自己沙发一下．

2008/5/5 天地之灵 <tdzl...@gmail.com>:

[silwile]

zan~

PS:请保持队形，标题[今天我们思考14] :)

2008/5/5 天地之灵 <tdzl...@gmail.com>:

这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

[silwile]

第9题已在[今天我们思考11]里面出现过了。建议以后大家发帖前去check一下今天我们思考的索引主题贴:-)

2008/5/5 天地之灵 <tdzl...@gmail.com>:

这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

[鋆邓]

哦，但数据范围大得多吧^_^

2008/5/5 silwile <sil...@gmail.com>:

[鋆邓]

恩，那个帖子的回帖里已经有人给出正确答案了

2008/5/5 鋆邓 <tdzl...@gmail.com>:

[pongba]

感谢鋆邓兄的题目！:-)

2008/5/5 天地之灵 <tdzl...@gmail.com>:

这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

10、第二道调剂的题目：
有2N张牌，编号从1到2N，现在开始洗牌，每次将牌从中间分成两堆，将前一半依次插入偶数位置，后一半依次插入奇数位置
比如N = 3时，一次操作后得到：
1 2 3 4 5 6
4 1 5 2 6 3
接下来继续这个操作，得到
2 4 6 1 3 5
1 2 3 4 5 6
我们会看到3次操作之后，所有的牌回到了原来位置。
现在，请你用一个期望复杂度在O(N)以内的算法，对于给定的N，求出多少次洗牌操作之后，所有的牌都回到了原来的位置。
并且，请尝试证明一下你的复杂度在O(N)以内。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[windstorm]

哇，这次一下子这么多题.......

2008/5/5 pongba <pon...@gmail.com>:

[pongba]

2008/5/5 天地之灵 <tdzl...@gmail.com>:

矩阵也疯狂（天地之灵收集整理）

1、费伯拉契数列：它是符合这样一个性质的数列：除了开头两个数以外，每个数都是之前两个数之和。
比如以0和1开头的费伯拉契序列叫做标准费伯拉契序列，有
 i    0  1   2   3   4   5   6   7   8
f(i)   0  1   1   2   3   5   8  13  21
现在，给你f(0)、f(1)、N和M，请你求出f(N)%M的值（即：编号为N的费伯拉契数除以M的余数）这四个数的范围都不超过2的32次方。

这一题，一开始我是想，难道不很简单么？fn mod m = fn-1 mod n + fn-2 mod m，递推就是了。但是我觉得这应该是误解了题意。如果就这么简单的话这题目也没意思了。于是进一步思考，难道说fn mod m有一个表达式可以直接算？fn是没有表达式，但不代表fn mod m没有。联想到mod运算的性质：任何一个数n mod m之后都落在0~m-1之间（可以将0~m-1标在一个m等分的圆环上）。fn有无穷多个，然而fn mod m的值却只可能有有穷多个，将无穷放在有穷里面，猜测应该会出现某种循环。所以我固定一个m，比如5，然后依次列出所有的fn mod 5，发现到f20的时候出现了循环，而且这个循环是从f0,f1开始的。f20的20和5有关系吗？4倍？不肯定。此外首次出现循环的点一定是从f0,f1开始的吗？也不确定。于是尝试另外的m，令m为3,4,6的时候都验证为从f0,f1开始重现循环。但开始发生循环的fx的那个x和m的关系尚不确定。

目前对于一定会循环只是归纳的结果，还需要证明一定会循环。经过一点考虑，发现，(fn, fn+1)作为一个pair，由于里面的fn只能位于0~m-1之间，所以这个pair只有m*m种可能性，所以必然至少有一个pair必然会在后续的序列中重现，而一旦重现，考虑到fn+2 = fn+1 + fn，于是某个局部序列便会重复它自身。

总结一下目前得到的结果：fn mod m这个序列并不像fn序列本身那样只能通过递归来求，实质上，fn mod m这个序列的信息量是有限的。至多衍生m*m位必然就会发生循环。所以当给定了一个m，我们只需首先求出那个循环点（O(m*m)），假设其下标是x，然后fn mod m就等于f (n mod x) mod m了。

首次循环一定是从f0, f1开始的结论待证。

... 走到家,想起来了. 关键是注意到从其它fn, fn+1首次开始循环的话,必然会得到"本应从fn-1就开始循环"的矛盾.

这个算法的复杂性只依赖于m,即O(m*m)(实际上是O(min(m*m, n)).如果要更好的话,除非在那个循环序列里面还有自身的规律.

[鋆邓]

太大了。M和N都是2的32次方之内

O(N)的算法都太大了，M*M更得不到什么效果。

2008/5/5 pongba <pon...@gmail.com>:

[pongba]

是O(min(m*m, n))

2008/5/5 鋆邓 <tdzl...@gmail.com>:

[duoduolo]

pongba wrote:

是O(min(m*m, n))

2008/5/5 鋆邓 <tdzl...@gmail.com>:

太大了。M和N都是2的32次方之内

O(N)的算法都太大了，M*M更得不到什么效果。

2008/5/5 pongba <pon...@gmail.com>:

2008/5/5 天地之灵 <tdzl...@gmail.com>:

矩 阵也疯狂（天地之灵收集整理）

1、费伯拉契数列：它是符合这样一个性质的数列：除了开头两个数以外，每个数都是之前两个数之和。
比如以0和1开头的费伯拉契序列叫做标准费伯拉契序列，有
 i    0  1   2   3   4   5   6   7   8
f(i)   0  1   1   2   3   5   8  13  21
现在，给你f(0)、f(1)、N和M，请你求出f(N)%M的值（即：编号为N的费伯拉契数除以M的余数）这四个数的范围都不超过2的32次方。

这一题，一开始我是想，难道不很简单么？fn mod m = fn-1 mod n + fn-2 mod m，递推就是了。但是我觉得这应该是误解了题意。如果就这么简单的话这题目也没意思了。于是进一步思考，难道说fn mod m有一个表达式可以直接算？fn是没有表达式，但不代表fn mod m没有。联想到mod运算的性质：任何一个数n mod m之后都落在0~m-1之间（可以将0~m-1标在一个m等分的圆环上）。fn有无穷多个，然而fn mod m的值却只可能有有穷多个，将无穷放在有穷里面，猜测应该会出现某种循环。所以我固定一个m，比如5，然后依次列出所有的fn mod 5，发现到f20的时候出现了循环，而且这个循环是从f0,f1开始的。f20的20和5有关系吗？4倍？不肯定。此外首次出现循环的点一定是从f0, f1开始的吗？也不确定。于是尝试另外的m，令m为3,4,6的时候都验证为从f0,f1开始重现循环。但开始发生循环的fx的那个x和m的关系尚不确 定。

目前对于一定会循环只是归纳的结果，还需要证明一定会循环。经过一点考虑，发现，(fn, fn+1)作为一个pair，由于里面的fn只能位于0~m-1之间，所以这个pair只有m*m种可能性，所以必然至少有一个pair必然会在后续的序 列中重现，而一旦重现，考虑到fn+2 = fn+1 + fn，于是某个局部序列便会重复它自身。

总结一下目前得到的结果：fn mod m这个序列并不像fn序列本身那样只能通过递归来求，实质上，fn mod m这个序列的信息量是有限的。至多衍生m*m位必然就会发生循环。所以当给定了一个m，我们只需首先求出那个循环点（O(m*m)），假设其下标是x，然 后fn mod m就等于f (n mod x) mod m了。

首次循环一定是从f0, f1开始的结论待证。

... 走到家,想起来了. 关键是注意到从其它fn, fn+1首次开始循环的话,必然会得到"本应从fn-1就开始循环"的矛盾.

这个算法的复杂性只依赖于m,即O(m*m)(实际上是O(min(m*m, n)).如果要更好的话,除非在那个循环序列里面还有自身的规律.

--

刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

囧。。。我回帖不看帖。。。

[鋆邓]

两项都很大，min一下也小不了。

2008/5/5 pongba <pon...@gmail.com>:

[pongba]

2008/5/5 鋆邓 <tdzl...@gmail.com>:

两项都很大，min一下也小不了。

我想说的是,只要m给定,无论n如何增长,都能在常数时间内计算出来.这已经比平凡的求法好多啦.
不过你应该是说还有更简单的,看样子m这个纬度上的复杂度应该不是O(m)就是O(1).O(1)的话等于就是能够有解析表达式了,不大可能啊.怎么降到O(m)是个问题.

[pongba]

2008/5/5 pongba <pon...@gmail.com>:

2008/5/5 鋆邓 <tdzl...@gmail.com>:

两项都很大，min一下也小不了。

我想说的是,只要m给定,无论n如何增长,都能在常数时间内计算出来.这已经比平凡的求法好多啦.
不过你应该是说还有更简单的,看样子m这个纬度上的复杂度应该不是O(m)就是O(1).O(1)的话等于就是能够有解析表达式了,不大可能啊.怎么降到O(m)是个问题.

在我感觉,m唯一可能的递推关系是将fn mod m表达为fn mod m-1,可以这样来表达:

X mod M = [ X mod M-1  + (X - X mod M-1) mod M ] mod M

这样的话,结合上面的做法,复杂度能够降到O(m).

难道还有更快的?

[pongba]

2008/5/5 pongba <pon...@gmail.com>:

2008/5/5 pongba <pon...@gmail.com>:

2008/5/5 鋆邓 <tdzl...@gmail.com>:

两项都很大，min一下也小不了。

我想说的是,只要m给定,无论n如何增长,都能在常数时间内计算出来.这已经比平凡的求法好多啦.
不过你应该是说还有更简单的,看样子m这个纬度上的复杂度应该不是O(m)就是O(1).O(1)的话等于就是能够有解析表达式了,不大可能啊.怎么降到O(m)是个问题.

在我感觉,m唯一可能的递推关系是将fn mod m表达为fn mod m-1,可以这样来表达:

X mod M = [ X mod M-1  + (X - X mod M-1) mod M ] mod M

这样的话,结合上面的做法,复杂度能够降到O(m).

难道还有更快的?

似乎这个递推公式无助于是，再想想..

[怀宇范]

好多好多，坐稳了满满看。。。

> 这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

>
> 10、第二道调剂的题目：
> 有2N张牌，编号从1到2N，现在开始洗牌，每次将牌从中间分成两堆，将前一半依次插入偶数位置，后一半依次插入奇数位置
> 比如N = 3时，一次操作后得到：
> 1 2 3 4 5 6
> 4 1 5 2 6 3
> 接下来继续这个操作，得到
> 2 4 6 1 3 5
> 1 2 3 4 5 6
> 我们会看到3次操作之后，所有的牌回到了原来位置。
> 现在，请你用一个期望复杂度在O(N)以内的算法，对于给定的N，求出多少次洗牌操作之后，所有的牌都回到了原来的位置。
> 并且，请尝试证明一下你的复杂度在O(N)以内。
>
>
> >
>

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo("
fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[hayate]

fibonacci数列本身有O(lgn)的求法，囧。不知道够不够.....

[dailiangren]

对啊，的确在前m*m个数中，一定会出现循环，这个结论的证明方法跟证明一个有理数一定是一个循环数对应一样的道理，用抽屉原则来证明

On May 5, 8:46 pm, pongba <pon...@gmail.com> wrote:
> 2008/5/5 天地之灵 <tdzl2...@gmail.com>:

[sanachilleus]

第一题：
令标准费伯拉契序列的第n项为F(n)，则
f(N) = f(N - 1) + f(N - 2)
= F(2) * f(N - 1) + F(1) * f(N - 2)
= F(2) * f(N - 3) + F(2) * f(N - 2) + F(1) * f(N - 2)
= F(3) * f(N - 2) + F(2) * f(N - 3)
= ...
= F(N) * f(1) + F(N - 1) * f(0)
所以原问题的复杂度就是F(N)的复杂度。

On 5月6日, 下午2时35分, dailiangren <dailiang...@gmail.com> wrote:
> 对啊，的确在前m*m个数中，一定会出现循环，这个结论的证明方法跟证明一个有理数一定是一个循环数对应一样的道理，用抽屉原则来证明
>
> On May 5, 8:46 pm, pongba <pon...@gmail.com> wrote:
>
>
>
> > 2008/5/5 天地之灵 <tdzl2...@gmail.com>:
>
> > > 矩阵也疯狂（天地之灵收集整理）
>
> > > 1、费伯拉契数列：它是符合这样一个性质的数列：除了开头两个数以外，每个数都是之前两个数之和。
> > > 比如以0和1开头的费伯拉契序列叫做标准费伯拉契序列，有
> > > i 0 1 2 3 4 5 6 7 8
> > > f(i) 0 1 1 2 3 5 8 13 21
> > > 现在，给你f(0)、f(1)、N和M，请你求出f(N)%M的值（即：编号为N的费伯拉契数除以M的余数）这四个数的范围都不超过2的32次方。
>
> > 这一题，一开始我是想，难道不很简单么？fn mod m = fn-1 mod n + fn-2 mod
> > m，递推就是了。但是我觉得这应该是误解了题意。如果就这么简单的话这题目也没意思了。于是进一步思考，难道说fn mod
> > m有一个表达式可以直接算？fn是没有表达式，但不代表fn mod m没有。联想到mod运算的性质：任何一个数n mod
> > m之后都落在0~m-1之间（可以将0~m-1标在一个m等分的圆环上）。fn有无穷多个，然而fn mod
> > m的值却只可能有有穷多个，将无穷放在有穷里面，猜测应该会出现某种循环。所以我固定一个m，比如5，然后依次列出所有的fn mod

> > 5，发现到f20的时候出现了循环，而且这个循环是从f0,f1开始的。f20的20和5有关系吗？4倍？不肯定。此外首次出现循环的点一定是从f0,f1开始-的吗？也不确定。于是尝试另外的m，令m为3,4,6的时候都验证为从f0,f1开始重现循环。但开始发生循环的fx的那个x和m的关系尚不确定。

>
> > 目前对于一定会循环只是归纳的结果，还需要证明一定会循环。经过一点考虑，发现，(fn,

> > fn+1)作为一个pair，由于里面的fn只能位于0~m-1之间，所以这个pair只有m*m种可能性，所以必然至少有一个pair必然会在后续的序列中重-现，而一旦重现，考虑到fn+2

> > = fn+1 + fn，于是某个局部序列便会重复它自身。
>
> > 总结一下目前得到的结果：fn mod m这个序列并不像fn序列本身那样只能通过递归来求，实质上，fn mod
> > m这个序列的信息量是有限的。至多衍生m*m位必然就会发生循环。所以当给定了一个m，我们只需首先求出那个循环点（O(m*m)），假设其下标是x，然后fn
> > mod m就等于f (n mod x) mod m了。
>
> > 首次循环一定是从f0, f1开始的结论待证。
>
> > ... 走到家,想起来了. 关键是注意到从其它fn, fn+1首次开始循环的话,必然会得到"本应从fn-1就开始循环"的矛盾.
>
> > 这个算法的复杂性只依赖于m,即O(m*m)(实际上是O(min(m*m, n)).如果要更好的话,除非在那个循环序列里面还有自身的规律.
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba

> > TopLanguagehttp://groups.google.com/group/pongba- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[sanachilleus]

第一题继续：
还用刚才用过的方法，
F(2N) = F(2) * F(2N - 1) + F(1) * F(2N - 2)
= F(3) * F(2N - 2) + F(2) * F(2N - 3)
= ...
= F(N) * F(N + 1) + F(N) * F(N - 1)
= F(N) * F(N) + 2 * F(N) * F(N - 1)

F(2N + 1) = F(2) * F(2N) + F(1) * F(2N - 1)
= ...
= F(N + 1) * F(N + 1) + F(N) * F(N)
= 2 * F(N) * F(N) + 2 * F(N) * F(N - 1) + F(N - 1) * F(N - 1)

所以F(2N)%M 和 F(2N + 1)%M都是O(lg(N))的复杂度。

> > > 5，发现到f20的时候出现了循环，而且这个循环是从f0,f1开始的。f20的20和5有关系吗？4倍？不肯定。此外首次出现循环的点一定是从f0,f1开始--的吗？也不确定。于是尝试另外的m，令m为3,4,6的时候都验证为从f0,f1开始重现循环。但开始发生循环的fx的那个x和m的关系尚不确定。

>
> > > 目前对于一定会循环只是归纳的结果，还需要证明一定会循环。经过一点考虑，发现，(fn,

> > > fn+1)作为一个pair，由于里面的fn只能位于0~m-1之间，所以这个pair只有m*m种可能性，所以必然至少有一个pair必然会在后续的序列中重--现，而一旦重现，考虑到fn+2

> > > = fn+1 + fn，于是某个局部序列便会重复它自身。
>
> > > 总结一下目前得到的结果：fn mod m这个序列并不像fn序列本身那样只能通过递归来求，实质上，fn mod
> > > m这个序列的信息量是有限的。至多衍生m*m位必然就会发生循环。所以当给定了一个m，我们只需首先求出那个循环点（O(m*m)），假设其下标是x，然后fn
> > > mod m就等于f (n mod x) mod m了。
>
> > > 首次循环一定是从f0, f1开始的结论待证。
>
> > > ... 走到家,想起来了. 关键是注意到从其它fn, fn+1首次开始循环的话,必然会得到"本应从fn-1就开始循环"的矛盾.
>
> > > 这个算法的复杂性只依赖于m,即O(m*m)(实际上是O(min(m*m, n)).如果要更好的话,除非在那个循环序列里面还有自身的规律.
>
> > > --
> > > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> > > TopLanguagehttp://groups.google.com/group/pongba-隐藏被引用文字 -
>

> > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[dailiangren]

f(N) 与 F(N) 分别代表什么意思？

 

---

dailiangren

2008-05-06

---

发件人： sanachilleus

发送时间： 2008-05-06 20:55:22

收件人： TopLanguage

抄送：

主题： [TopLanguage] Re: 矩阵也疯狂（天地之灵5月5日收集整理）

[王良晶]

太赞了~~

[鋆邓]

太fz了，你居然冒出来了
PS: 第三题就是lamSempr大牛以前考我的题目。

2008/5/6 王良晶 <IamS...@gmail.com>:

太赞了~~

> 这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

[王良晶]

没有吧……没印象了

On May 7, 8:51 pm, "鋆邓" <tdzl2...@gmail.com> wrote:
> 太fz了，你居然冒出来了
> PS: 第三题就是lamSempr大牛以前考我的题目。
>

> 2008/5/6 王良晶 <IamSe...@gmail.com>:

[pongba]

2008/5/7 鋆邓 <tdzl...@gmail.com>:

太fz了，你居然冒出来了
PS: 第三题就是lamSempr大牛以前考我的题目。

在10月28日举行的2007ACM/ICPC国际大学生程序设计竞赛亚洲区域赛(南京)中，我校学子取得一金一铜的优异成绩，来自我校电工电子科技创新中心张伟、周郴、王良晶组成的团队实现了我校ACM国际竞赛金牌零的突破。本次比赛在南京航空航天大学举行。

    2007年ACM/ICPC国际大学生程序设计竞赛亚洲区域赛(南京)有来自全国各地95所高校的658支参赛队，经过激烈角逐，我校在网络预赛中以13名和27名的成绩取得晋级区域赛的两个名额。在为期两天的决赛中，张伟、周郴、王良晶组成的团队以总成绩第八名获得了金牌。另外杜鹏、刘绍辉、陈建群获得铜牌。

-========Orz的分割线=========-

牛人啊！:-)

[sanachilleus]

第二题：
这一题要分成两种情况：k >= N 或者 k < N；
先说k >= N 的情况。
这种情况比较简单，就是让我们在N - 1级台阶中自由的选择"落脚点"。每种选择对应一种爬楼方法。
由于每级台阶都有被选中和不被选中两种可能，所以一共有2^(N - 1)种可能。注意到：
2^(2N) % M = (2^N % M)^2 % M； 2^(2N+1) % M = (2 * (2^N % M)^2) % M
所以2^(N - 1)的复杂度是O(lg(N))
记N级台阶的上楼方法数为P(N),于是当 N <= k时P(N) = 2^(N-1)。
对于k < N 的情况，容易得到：
P(N) = P(N-1) + P(N-2) +...+ P(N-k)
= P(1) * P(N-1) + P(1) * P(N-2) +...+ P(1) * P(N-k)
= P(2) * P(N-2) +...+ P(2) * P(N-k) + P(1) * P(N-k-1)
= P(3) * P(N-3) +...+ P(3) * P(N-k) + (P(1) + P(2))*P(N-k-1) + P(2)
* P(N-k-2)
=...
= P(k) * P(N-k) + (P(1)+P(2)+...+P(k-1))*P(N-k-1) + (P(2)+P(3)+...
+P(k-1))*P(N-k-2) + ... + P(k-1) * P(N-2k+1)
又有P(N-k) = P(N-k-1) + P(N-k-2) + ... + P(N-2k)，所以
P(N) = P(k+1)*P(N-k-1) + (P(2)+P(3)+...+P(K))*P(N-k-2) + ... + P(k) *
P(N-2k)
= ...
用这种方法，对于任意的0 <= t < k，{P((2x)k + t)}和{P((2x+1)k + t)}都可以用{P(xk + t)}和
{P(t)}表示，
而{P(t)}的复杂度已经在情况一中讨论过，为O(lg(t))。所以情况二的复杂度是O(lg(N)*t^2)



On 5月7日, 下午8时59分, 王良晶 <IamSe...@gmail.com> wrote:
> 没有吧......没印象了

> > > > 并且，请尝试证明一下你的复杂度在O(N)以内。- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[hayate]

...... 你是HUST 的 Sempr?...

Orz....

2008/5/7 王良晶 <IamS...@gmail.com>:

[sanachilleus]

第四题：
记长度为2N米的走廊铺砖块的方法数为P(N)，显然P(1) = 3。另外另P(0) = 1，容易得出当N > 1时
P(N) = 3P(N-1) + 2P(N-2) + 2P(N-3) + ... + 2P(0)
= 3P(N-1) - P(N-2) + (3P(N-2) + 2P(N-3) + ... + 2P(0))
= 3P(N-1) - P(N-2) + P(N-1)
= 4P(N-1) - P(N-2)
对于确定的N，用归纳法容易证明，对于任意1 <= i < N-1，
P(N) = 1/2((P(i+1)-P(i))*P(N-i) - (P(i)-P(i-1))*P(N-i-1))
然后，我们又可以用P(N)， P(N-1)，P(1)和P(0)来表示P(2N)和P(2N+1)了，于是原问题复杂度是
O(lg(N))。

On 5月7日, 下午10时18分, hayate <hayate...@gmail.com> wrote:
> ...... 你是HUST 的 Sempr?...
> Orz....

> 2008/5/7 王良晶 <IamSe...@gmail.com>:
>
>
>
> > 没有吧......没印象了

[sanachilleus]

第三题没看懂，当N >= 3时，项链的种类不是和N无关吗？因为只要3色宝石的排列顺序确定，项链不就确定了吗？请问我的理解错在什么地方？

> > - 显示引用的文字 -- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Eric]

pangba 你想想 要算一个周期的长度的话 要不要 m^2.
我觉得这个是突破口

另外 O(1) 的算是不可能的，这个问题是大难题， 我就知道有人专门写博士论文算 Fib mod n 的周期。

[pongba]

2008/5/10 Eric <xu.ma...@gmail.com>:

pangba 你想想 要算一个周期的长度的话 要不要 m^2.
我觉得这个是突破口

恩，我也是这么想的。发现里面还有小周期（如，对于0来说）。

[鋆邓]

1、
我们分析 F(N) = F(N-1)+F(N-2)，这是一个显然的线性递推问题。
如果我们将F(N)和F(N-1)组成向量A(n) =( F(N), F(N-1) )
那么就有
F(N+1) = 1* F(N) + 1*F(N-1)
F(N)     = 1*F(N)  + 0*F(N-1)
A(n+1) = ( F(N)+F(N-1), F(N) )
= A(n) *B

其中B = 1 1
             1 0

那么，设A(0) = (F(1), F(0))
则有A(N) = A(0) * B^N
F(N) = (A(0) * B^N) [1]　　（其中[1]指取出该向量的第二项，这里用了C语言的思维理解向量和矩阵）
     = F(1) * ((B^N)[1][0] + F(0) * ((B^N)[1][1])
对于求B^N，我们有lgN的算法来求矩阵的幂。并且，整个运算过程中没有减法和除法，因此我们可以在运算过程中将所有的加法当作模加来计算，所有乘法当作模乘来计算。

2008/5/10 pongba <pon...@gmail.com>:

[pongba]

2008/5/10 鋆邓 <tdzl...@gmail.com>:

1、
我们分析 F(N) = F(N-1)+F(N-2)，这是一个显然的线性递推问题。
如果我们将F(N)和F(N-1)组成向量A(n) =( F(N), F(N-1) )
那么就有
F(N+1) = 1* F(N) + 1*F(N-1)
F(N)     = 1*F(N)  + 0*F(N-1)
A(n+1) = ( F(N)+F(N-1), F(N) )
= A(n) *B

其中B = 1 1
             1 0

那么，设A(0) = (F(1), F(0))
则有A(N) = A(0) * B^N
F(N) = (A(0) * B^N) [1]　　（其中[1]指取出该向量的第二项，这里用了C语言的思维理解向量和矩阵）
     = F(1) * ((B^N)[1][0] + F(0) * ((B^N)[1][1])
对于求B^N，我们有lgN的算法来求矩阵的幂。并且，整个运算过程中没有减法和除法，因此我们可以在运算过程中将所有的加法当作模加来计算，所有乘法当作模乘来计算。

这个不就是hayate说的logN求fib(n)的算法？

但如果我没弄错的话，这个算法的复杂性比我一开始给的那个高啊，对于任意给定的M，

1. 你的算法复杂度是O(logN)
2. 我的算法复杂度是O(1)

[鋆邓]

你的算法是O(M^2)
M的范围也是很大的
你没有办法在有效时间内做好预处理。
另外，如果你打算做这样的预处理，你需要对每个给定的M都进行计算，你没有足够的空间保存这样的一个表

2008/5/10 pongba <pon...@gmail.com>:

[鋆邓]

恩，可能是我没表达清楚。
对于多组数据而言，M可能互不相同。

2008/5/10 鋆邓 <tdzl...@gmail.com>:

[pongba]

2008/5/10 鋆邓 <tdzl...@gmail.com>:

你的算法是O(M^2)
M的范围也是很大的
你没有办法在有效时间内做好预处理。
另外，如果你打算做这样的预处理，你需要对每个给定的M都进行计算，你没有足够的空间保存这样的一个表

呃，任意一次计算总是给定M的吧。
另，你的算法并没有用到mod M的性质吧。

我们这两个方法的复杂性似乎应该这样来比较，由于涉及到M和N这两个变量，可以假想算法耗时间可以描绘在一个三维空间上的一个二维曲面（但变量的算法复杂性是一个曲线），问题就直观的变成哪个曲面在"上面"的问题，这个很好办，只要给定坐标M,N看哪个曲面的值大就行了，在任一一个M切割出来的平面上，只要N充分大，我的算法的曲面就会在下面，因为只依赖于M。但如果给定N的话，只要M足够大，你的算法就更快。（这是什么曲面啊？靠）

我发现可以结合起来，降到logM^2即O(logM)

[pongba]

2008/5/10 pongba <pon...@gmail.com>:

2008/5/10 鋆邓 <tdzl...@gmail.com>:

你的算法是O(M^2)

M的范围也是很大的
你没有办法在有效时间内做好预处理。
另外，如果你打算做这样的预处理，你需要对每个给定的M都进行计算，你没有足够的空间保存这样的一个表

呃，任意一次计算总是给定M的吧。
另，你的算法并没有用到mod M的性质吧。

我们这两个方法的复杂性似乎应该这样来比较，由于涉及到M和N这两个变量，可以假想算法耗时间可以描绘在一个三维空间上的一个二维曲面（但变量的算法复杂性是一个曲线）

打错字了，是"单"变量的算法复杂性是一条曲线。

[鋆邓]

结合不了
用logN的方法，错过了其中大部分的具体值，你无法判断是否出现了循环。

2008/5/10 pongba <pon...@gmail.com>:

[pongba]

2008/5/10 Eric <xu.ma...@gmail.com>:

pangba 你想想 要算一个周期的长度的话 要不要 m^2.
我觉得这个是突破口

另外 O(1) 的算是不可能的，这个问题是大难题， 我就知道有人专门写博士论文算 Fib mod n 的周期。

在哪？贴出来orz一下:)

[pongba]

2008/5/10 鋆邓 <tdzl...@gmail.com>:

结合不了
用logN的方法，错过了其中大部分的具体值，你无法判断是否出现了循环。

寒，发现我原先的复杂性弄错了，应该是O(M^4)，因为要预先计算前（最多）M^2项数列值，其中每一项的计算都是O(M^2)。

这样的话就可以结合了，因为你的方法用来计算每一项的话可以将其复杂度降为log M^2即O(logM)，于是整个复杂性降为O(M^2 * logM)

[鋆邓]

- - 显然不用，计算每一项的值可以O(1)的从之前一项得到

2008/5/10 pongba <pon...@gmail.com>:

[pongba]

2008/5/10 鋆邓 <tdzl...@gmail.com>:

- - 显然不用，计算每一项的值可以O(1)的从之前一项得到

-_-|||低级错误

[rockeet]

很多这些问题，归根结底都是排列组合的问题。所以要学好组合数学啊！

[Eric]

邓兄的方法巧妙, 附带说一个可能大家都知道

矩阵B 的特征值就是 Fib 数列里面 a^n + b^n 的 a 和 b, 有兴趣的可以研究一下为什么. :)

[鋆邓]

对于第二题，我们可以采用类似第一题的方法，那么，我们所计算的向量，其维度恰好等于k（为什么，自己思考）因此，我们所计算的矩阵，也恰好是k阶的。矩阵的形式大致如此：
1 1
1 0 1
1 0 0 1
1 0 0 0 1
.
.
1 0  . . .     1 0
1 0  . . .     0 1
1 0  . . .     0 0
当然，如果你选用矩阵左乘一个列向量的思维，可以获得一个稍微看起来舒服一点的矩阵——第一行全部是1，第二行开始斜向右下（也就是上述矩阵的转置）。但是这两个矩阵的本质是一样的。

那么，我们就已经有了一个O(k^3*lgN)的算法，如果你嫌这个复杂度高了，许多算法书籍上你能找到一种求矩阵乘法的分治算法，通过减少乘法的次数而把计算一次矩阵乘法的复杂度降低到k^2.81左右。不过，这个意义不大，不是么……

2008/5/5 天地之灵 <tdzl...@gmail.com>:

这个范围使你的计算机不能模拟整个过程了，所以——思考新的算法吧。

[鋆邓]

补充一个知识：
上文所提到的k^ 2.81次方的矩阵乘法算法叫做Strassen算法，是一种基于分治思想的矩阵乘法，
http://blog.csdn.net/chief1985/archive/2008/05/06/2402553.aspx
其效率的提升不仅仅在于复杂度的降低，更大程度在于使用加法和减法取代了许多乘法运算，对于浮点数矩阵，这个性能提升十分明显。在目前的计算机环境下，对于整数计算，这个效果并不是那么明显（但依然可以观察到性能的提升）。

2008/5/11 鋆邓 <tdzl...@gmail.com>:

[鋆邓]

第三题，我们同样可以观察到，如果把整个环解开，看作一条链，以每个位置结束的统计数，只和上一次的每个位置的三种颜色的统计数相关。
因此，我们以向量[Ri,Yi,Bi] 来表示到第i位置为止的统计数，
那么，例如R后面不能有B的情形，我们有
R(i+1) = Ri + Yi + Bi
Y(i+1) = Ri + Yi + Bi
B(i+1) =  0  + Yi + Bi
因此
[Ri, Yi, Bi] = [R1, Y1, B1] * A^(i-1) （注意这里我们偶然的从1开始计算，因为我们认为项链至少有一个珠子）
其中A 为矩阵：
1 1 0
1 1 1
1 1 1

注意到我之前的描述刻意避过了R1、Y1、B1的取值，因为我们题目要求的是一个环。如何把链转化为环呢？我们有两种思路：
1、对每一种颜色的开头，限制某些颜色的结尾。对于结尾颜色不符合要求的，不予统计
2、为何我们不求出N+1长度的链，但是要求首尾两个相同呢

不论哪一种思路，我们都会需要计算这样一个东西：开头和结尾符合某一个条件的统计
这就是为什么我开头忽略了R1、Y1、B1的取值：我们可以通过更改它们的取值来确定开头珠子的颜色，用最终乘得向量中的某一项来确定结尾珠子的颜色。换言之，如果我们用第二种思路，那么我们可以计算这三个值的和：
R = [1,0,0] * A(i+1 -1) [0]  (后面的[0]表示取出向量的第一个元素，下面类似)
Y = [0,1,0] * A(i+1 -1) [1]
B = [0,1,1] * A(i+1 -1) [2]

如果你更加细心的观察上面并排写的这三个横向量，其实组成了一个单位矩阵，并且后面的[0] [1] [2]，就是求得 A^(i+1-1)即A^i的：
第一排第一个数、第二排第二个数、第三排第三个数
我们的最终答案就是这三个数的和

PS: 用[1,0,0]去乘，相当于取出矩阵的第一行，[0,1,0]相当于取出第二行，[0,0,1]相当于取出第三行
用矩阵乘法的定义很容易看出。

其他的，比如加法和乘法转变为模加和模乘，就不用我再多说了吧

[鋆邓]

第四题没有什么特别的思路，如果你真的理解了线性递推向矩阵的转化，这题完全是送分的（如果有分的话……）
这一题只是略有些麻烦而已：我们从左往右来排布这个矩阵，一次排一格，计算出每一种状态：即，每个位置是否凸起（是否它之前已经有了一个连续的半块），那么，至多只有2^3种状态，认真地找出这些状态的变化关系，并写下递推矩阵就可以了
它们的递推关系是指：一个状态可以通过放下一些砖块，在下一个位置构成的形状，而之前的状态已经布满。
比如说，
1
1
0
可以通过放一个砖块，变成
1 0
1 0
1 1
，那么我们认为状态110(2)也就是状态6，可以转化为状态001(2)也就是状态1，也就是说x6'的线性递推式中，将有一项 1* x1。

要当心一个额外的陷阱，它容易导致你写错递推式：比如依然说这个情形
1
1
2 2
我们知道它可以包含一个有000(2)状态，放下两个砖块而得到的，也可以表示一个110(2)状态放下一个砖块得到的，你的递推式必须不能重复统计这两个状态。比如加以限制：状态的转换必须包含至少一个到达当前位置的砖块（除去111-000这唯一的一个例外）
如果你这样做了，你可能会发现自己存在这样的一种需求：统计从当前位置（注意不是之前的位置）的000，到当前位置的110的转换。
注意，你必须意识到，这里x6'是有一项x0'，而不是x0，你应该将这个x0'再次展开成为一个表达式（在我写的递推式里，x0' = x7)
也就是说，你的递推式必须是从之前状态而来的。（引申：对于存在之前的之前状态的递推式，将若干个之前状态联合成为一个向量，并且在后面部分简单的使用一个斜矩阵来"移动"多个之前状态：参考第二题的矩阵）

你必须认真地思考自己的递推式。
当你的递推式没有问题之后，一切就都解决了——简单的取N次方，然后求得最终的111这样一个状态（也就是x7）的取值，并当作结果输出。

当然，一个8*8的矩阵乘法需要耗费不少时间，如果你希望进一步提高效率，你会注意到，这里有些状态是不必要的：
1、111可以转化成下一状态的000，并且转化之后不再需要它
2、110和011状态永远一样，100和001也是一样
3、010状态永远不会出现
4、如果你一次计算两格，那么就不会出现100、111这样的状态
最终，我们可以把这个矩阵优化成一个3*3的，效率进一步提高。

[鋆邓]

没人回帖了，不好玩……
明天贴出第四题的解法，从这题开始每题都涉及一个新的思路。

[windstorm]

现在注意力都在地震上面......

2008/5/13 鋆邓 <tdzl...@gmail.com>:
> 没人回帖了，不好玩......

> > 这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

[鋆邓]

好吧……那我休息两天……正好这周末出差，到了外地再抽空继续写解题报告

2008/5/13 windstorm <likunar...@gmail.com>:

[鋆邓]

第五题，有了第一题的参考，我们应该很容易根据M、N很大以及对M取余，思考到我们应该用类似第一题的矩阵的办法来解决这个问题。
为了区分本题解法中出现的多个矩阵，我们首先把第一题解法中的矩阵命名为F矩阵：
F =
1 1
1 0
并且我们知道
F^i [0][1] = F^i [1][0] = f(i) 即：F的i次方，左下、右上角的数为标准费伯拉契数列的第i个数）
我们所要求的数是
Σ(对i从1到N) f(a*i+b)
= Σ(对i从1到N) F^(ai+b)[0][1]
= (Σ(对i从1到N) F^(ai+b))[0][1]  (根据矩阵加法的定义)
= (F^b * Σ(对i从1到N) F^ai ) [0][1]
= (F^b * Σ(对i从1到N) (F^a)^i) [0][1]
（矩阵的乘法和乘方符合许多实数乘法/乘方的性质，比如对加法的分配率、乘法自身的结合率等。另外强烈提醒一点：矩阵乘法是不具有交换率的。）
对于求解这个式子，我们可以预先求出F^b和F^a，可是Σ(对i从1到N) (F^a)^i在N很大的时候有没有什么好的办法呢？
令B  = F^a，我们实质上需要一个算法，对于给定的B，求解
Σ(对i从1到N) B^i
假如B是一个实数，那么我们可以用等比数列求和公式来解决（注：如果能容忍精度损失，矩阵也可以用该公式求解，因为同样符合其性质）
该公式类似于：
  a0 - an
---------------
     1 - p
其中p为等比数列的公比。

但是我们这里不能使用这个公式，不是因为我们求解的对象是矩阵，而是我们的题目有一个很特殊的要求，正是出于该要求我们才选择矩阵这样一个工具的：对M取余！同余定理的公式中不存在除法，对余数保留的要求让我们不能选用这个公式。
所幸，矩阵本身就可以更加完美的解决这个问题（甚至也可以解决实数的等比求和）
考虑我们所说的"线性递推"问题，求和问题完全符合这个性质：
Ai = B * A(i-1) + 0 * S(i-1) （这里字母B是我们上文所说的矩阵的"公比"，当然，如果存在其他类似问题，B可以替换成任何矩阵）
Si = I * A(i-1) + I * S(i-1) （字母I表示单位矩阵，单位矩阵乘上任何矩阵等于该矩阵本身）
这里Si表示从A0到Ai-1所有数的和，并且S0 = O (字母O表示0矩阵）
那么，如果把Ai和Si组成一个类似"向量"的东西（实际上这是一个2*4的矩阵)，那么我们就可以构建出对应的递推矩阵，其形式如下：
C =
B I
O I 
这是个4*4的矩阵，有四个2*2的矩阵拼成。分块矩阵相乘相对于每一块的规则和普通矩阵相乘相对于每个元素的规则一样（甚至不论每一块的大小是否相等，只要能够正确的相乘），因此我们无需担心这个过程和我们之前矩阵解线性递推式的过程有任何不同。

因为我们之前的需求是从B^1开始计算，所以用[A1,S1]也就是[B,O]去左乘它的N次方，取出后两列，就得到了B^1 + B^2 + B^3 + B^4..... + B^N
另外，我们注意到如果用[I, O]去左乘它的N次方，取出后两列得到的是从I开始，一直求和到B^(N-1)为止，
又有用[I,O]去左乘它，实质上等同于取出它的前两行，因此实质上C^N的右上角部分，就等同于从I到B^(N-1)这N项的和，这是这个矩阵很重要的一个性质。

到此位置，我们已经将原本一个摸不着思路的奇怪的题目，转化成求一个2*2矩阵的幂，和求一个4*4矩阵的幂，外加若干有限次的矩阵乘法了，但归根到底我们的思路还是线性递推向矩阵的转化而已，您理解了这个过程了么？

2008/5/5 天地之灵 <tdzl...@gmail.com>:

这个范围使你的计算机不能模拟整个过程了，所以——思考新的算法吧。

[鋆邓]

下面到第六题了，我得承认，相对前面几题来说，这题的思路相当恶心。
我们首先要冷静下来，抛弃掉刚刚用线性递推解决掉那么复杂而有趣的问题的喜悦，因为直觉告诉我们这题不再像之前那样简单（您有这样的直觉么？）
冷静下来以后，我们仔细看一下题目。抛弃掉枯燥难理解的描述式，我们观察到，题目要求我们所求的，是一条条斜杠走向（/这个方向）上的数字的和。好吧，斜杠这个描述让我们更加晕乎，那么我们的注意力关注到另一个地方去：
题目中所说的 (J+i)%k = b，意味着每一行、每一列，所被加上的两个数字，之间的距离都是k个数（也就是它们之间有k-1个没有被计算的数）
这意味着什么呢? 暂时还是不那么好想到，那么我们的注意力继续转移到另一个条件：杨辉三角
我们知道，所谓杨辉三角，其实就是组合数按照一定形式排列在一起，组合数当中的某些项……间隔k……你想到了什么了么？
假设我们有个这么个i，使得i^k = 1，并且i^1、i^2、i^3.... i^k-1次方都不是实数（好吧，这里偷来了虚数i的概念，虽然实际上指的不是那个东西，虚数i并不是符合这里k=4的一个值），那么，考虑
(1+i)^N = C(0,N) * 1 + C(1,N) * i + C(2,N)* i^2 + ...+ C(k,N) * 1 + C(k+1,N)* i +... + C(N,N)*i^(N%k)
够猥琐够恶心吧，可惜理想很美好，现实中我们怎样去找这么一个i，并且让它能符合大部分的运算性质呢？（符合运算性质这一点十分重要） 数学的定义必须是十分严谨的，我们不能根据我们的需求就随便去创造这样一个概念，我们得求助于一个什么东西……
如果你的知识范畴足够广阔，你就应该听说过一个叫做"置换"的东西，它是1到k这k个数的一个排列，譬如这样一个置换

1 2 3 4 5

2 3 4 5 1
意味着进行一次置换，所有1变为2，2变为3，3变为4，4变为5，5变为1，并且，我们所说的置换空间里的"幺元"（幺元是群论中的概念，它意味着在一个计算空间中，一个元素具有1的性质：任何数乘上它，等于它乘上该数，等于该数本身），是完全不变的置换：1 2 3 4 5。
那么很显然，之前所列出的2 3 4 5 1这样的置换，任何数经过5次相同的置换，就得到了该数本身，换言之，2 3 4 5 1置换的5次方，等于1 2 3 4 5这个幺元。
好吧，我认为我们已经接近了。可惜置换这个东西虽然符合i^k = 1，以及i^1、i^2、i^3 .. i^k-1都不是实数这些要求，它却有致命的一些缺陷：1、将置换乘上一个实数是无意义的。2、置换不能相加。这样我们的设想就完全无用武之地了。因此，我们得寻找一些更好的东西来代替置换。
对，矩阵。
一个k阶置换可以对应这一个矩阵，这个矩阵是k阶的，其行列式为1或-1，q

[鋆邓]

(PS)刚不小心按到发送，继续补上后续内容

下面到第六题了，我得承认，相对前面几题来说，这题的思路相当恶心

。
我们首先要冷静下来，抛弃掉刚刚用线性递推解决掉那么复杂而有趣的问题的喜悦，因为直觉告诉我们这题不再像之前那样简单（您有这样的直觉么？）
冷静下来以后，我们仔细看一下题目。抛弃掉枯燥难理解的描述式，我们观察到，题目要求我们所求的，是一条条斜杠走向（/这个方向）上的数字的和。好吧，斜杠这个描述让我们更加晕乎，那么我们的注意力关注到另一个地方去：
题目中所说的 (J+i)%k = b，意味着每一行、每一列，所被加上的两个数字，之间的距离都是k个数（也就是它们之间有k-1个没有被计算的数）
这意味着什么呢? 暂时还是不那么好想到，那么我们的注意力继续转移到另一个条件：杨辉三角
我们知道，所谓杨辉三角，其实就是组合数按照一定形式排列在一起，组合数当中的某些项……间隔k……你想到了什么了么？
假设我们有个这么个i，使得i^k = 1，并且i^1、i^2、i^3.... i^k-1次方都不是实数（好吧，这里偷来了虚数i的概念，虽然实际上指的不是那个东西，虚数i并不是符合这里k=4的一个值），那么，考虑
(1+i)^N = C(0,N) * 1 + C(1,N) * i + C(2,N)* i^2 + ...+ C(k,N) * 1 + C(k+1,N)* i +... + C(N,N)*i^(N%k)
够猥琐够恶心吧，可惜理想很美好，现实中我们怎样去找这么一个i，并且让它能符合大部分的运算性质呢？（符合运算性质这一点十分重要） 数学的定义必须是十分严谨的，我们不能根据我们的需求就随便去创造这样一个概念，我们得求助于一个什么东西……
如果你的知识范畴足够广阔，你就应该听说过一个叫做"置换"的东西，它是1到k这k个数的一个排列，譬如这样一个置换

1 2 3 4 5

2 3 4 5 1
意味着进行一次置换，所有1变为2，2变为3，3变为4，4变为5，5变为1，并且，我们所说的置换空间里的"幺元"（幺元是群论中的概念，它意味着在一个计算空间中，一个元素具有1的性质：任何数乘上它，等于它乘上该数，等于该数本身），是完全不变的置换：1 2 3 4 5。
那么很显然，之前所列出的2 3 4 5 1这样的置换，任何数经过5次相同的置换，就得到了该数本身，换言之，2 3 4 5 1置换的5次方，等于1 2 3 4 5这个幺元。
好吧，我认为我们已经接近了。可惜置换这个东西虽然符合i^k = 1，以及i^1、i^2、i^3 .. i^k-1都不是实数这些要求，它却有致命的一些缺陷：1、将置换乘上一个实数是无意义的。2、置换不能相加。这样我们的设想就完全无用武之地了。因此，我们得寻找一些更好的东西来代替置换。
对，矩阵。

一个k阶置换可以对应这一个矩阵，这个矩阵是k阶的，其行列式为1或-1，并且除每行、每列各有一个1以外，其他元素全部为0。
从置换得到一个置换矩阵的方法是：将置换的第i行，第i置换的结果列，设置为1。
譬如我们刚才提了几次的那个置换，对应着这样一个矩阵：
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
我们很容易观察到，这个矩阵符合性质i^k = I （这里不再是1，而是单位矩阵I），并且i的0到k-1的不同次方如果加在一起，完全不会互相干扰（它们分布在不同的斜线上），这是一个足够完美以解决我们问题的那个i！
接下来我们只需要把问题更加具体化一点，用含有这个矩阵（我们暂时命名它为P矩阵）的式子来解决这个问题。
首先简单起见，考虑(j+i)%k = 0，那么：
对于第一行： (I+P)^0
第二行：(I+P)^1/P^1    (PS: 这里是一个我们可以轻松的处理/P的情形，因为我们知道 P^k = I，那么I/P = P^(k-1))
第三行：(I+P)^2/P^2
.
.
.
换言之，我们需要求出所有(1+P)/P的不同次方的和（用上一题的方法），然后取出第一行第一列的数（其实是因为对角线上的数代表了我们所谓的"实数"）。
那么，对于(j+i)%k = b的情形，我想你也应该知道怎么做了：
对上面的整个式子（也就是说，最后结果）乘上P^b次方，再取出第一行第一列的数。
如果你还不知道为什么，仔细想想吧……

2008/5/14 鋆邓 <tdzl...@gmail.com>:

[鋆邓]

第7题：
1、我们能直接想到，一个当前的"状态"只和每人门前花朵的奇偶性有关，我们可以用1或者0去表示。
2、仔细构想整个状态变化过程，发现用线性递推没有问题，只是对应修改为模2加和模2乘。
3、如果A愿意在B的门前放一朵花，表示为矩阵的第A行第B列为1。（为什么不是第B行第A列？这里需要仔细思考！行和列弄反很容易带来错误。正确的思路是回想一下矩阵乘法的过程。另外，线性递推式的转置才是右乘所选择的矩阵，因为线性递推式本身应看作矩阵左乘其列向量）
4、每个人自己门前的花保留，而不是每天清楚，表示为矩阵的第A行第A列（即整个对角线）全部为1。
5、如果你不能理解上面两点和矩阵的关系，把线性递推式列出来吧。
6、跟恶心的前一题相比，这题毫无难度。不是么？

[lfw]

第8题题干内容有误。

On 5月5日, 下午6时45分, 天地之灵 <tdzl2...@gmail.com> wrote:

> 8、再来一题，让你们知道矩阵不仅仅是矩阵，它不是一个人在战斗！
> 有一种k-电路矩阵，它有k个输入和k个输出，输入和输出都只有两种状态：高电位或低电位，输出和输出布成一个k*k的二极管矩阵，电子二极管的状态可
> 以通过激光设置，也具有两种状态：通过与不通过。
> 换言之，每个输出和输入当中的某些相通。如果所有与它连通的输入中存在一个高电位，那么输出为高电位。如果所有与它连通的输入全部为低电位，则输出低电
> 位。
> 现在，将N块相通k-电路矩阵一个接一个拼接成一串，每块电路的输入按照顺序连接到下一块电路板上。
> 现在，给定k个输入源的输入状态，求出最终一块电路板的k个输出的状态。
> k不超过100，而N不超过2的32次方。
>

其中，“现在，将N块相通k-电路矩阵一个接一个拼接成一串，每块电路的输入按照顺序连接到下一块电路板上。”

正常逻辑应该是：
<1>每块电路的输"出"按照顺序连接到下一块电路板上；
或者
<2>每块电路的输入按照顺序连接到“上”一块电路板上；
选择其一
否则，输入输出不是变数大了？

[鋆邓]

恩，是把输入连到下一块电路板的输出上。

2008/5/15 lfw <zhoub...@gmail.com>:

[pongba]

多谢邓兄的解题报告:-)

2008/5/15 鋆邓 <tdzl...@gmail.com>:

[鋆邓]

休假今天结束，明天开始上班，贴出剩下几题的报告
第八题：
其实我们可以看出这一题和矩阵实在有太直接的相似之处，不同的是我们发现从我们刚才已经几乎熟悉了的加法和乘法，变成了二进制的"或"和"与"：
1、输入状态是一个向量，每一个元素是0或者1
2、一块电路矩阵就是一个矩阵A，每一个元素是0或者1（连通或不连通）
3、输入状态B和输出状态B'满足如下的关系：
B'[0] = B[0]&A[0][0] | B[1]&A[1][0] | B[2]&A[2][0] | B[3]&A[3][0]...
B'[1] = B[0]&A[0][1] | B[1]&A[1][1] | B[2]&A[2][1] | B[3]&A[3][1]...
.
.
.
这几乎就是矩阵的线性递推过程的翻版。

4、那么，如果有电路矩阵A和A1，且B (A)==> B' (A1)==>B'' （下面的&指与运算，|指或运算）
B''[0] = B'[0]& A1[0][0] | B'[1] & A1[1][0] | ....
        = (B[0] & A[0][0] | B[1] & A[1][0] | B[2]&A[2][0] ...)&A1[0][0] | (B[0]&A[0][1] | B[1] & A[1][1] | B[2] & A[2][1] ...)&A1[1][0] ....
        = B[0] & A[0][0] & A1[0][0] | B1&A[1][0]&A1[0][0]..... ..  | B[0]&A[0][1]&A1[1][0] | B[1]&A[1][1] & A1[1][0]
        = B[0] &( A[0][0]&A1[0][0] | A[0][1] & A1[1][0] | A[0][2]&A1[2][0] ....) | B[1] & (A[1][0]&A1[0][0] | A[1][1] & A1[1][0] | A[1][2]&A1[2][0]) ...
那么，假设有B(A') ==>B''
则有
A''[i][j] =A[i][0]&A1[0][j] | A[i][1]&A1[1][j] .....
你明白了么？ 也就是说，如果我们把二进制的或看做是加法，与看做是乘法，这样的运算空间里，矩阵乘法的性质仍然存在。我们依然可以用第一节中就说到的方法，来k^2.81 * log(N)的复杂度来求得结果。

思考：如果反过来，与变成或，或变成与，还符合这样的性质么？

我猜您会觉得不符合，然而实际上也是符合的，把上面的推导与换成或，或换成与，整个推导过程依然成立
很容易理解，能使上述推导成立的两种运算符，都可以用矩阵的方法来求。这两种运算符必须符合：（以下+和*各指代一种运算符，不单单指实数范围内的加法和乘法
1、+对*拥有分配律。也即：(a + b)* c = a*c + b*c
2、+具有交换率和结合率。 也即：a+b = b+a   (a+b)+c = a+(b+c)
3、*具有结合率。 也即：(a*b)*c = a*(b*c)

只要符合这些定律的运算符，都可以用于矩阵乘法的公式。思考如下的运算符组合：
1、 | 和 & （这一道题目就这样解决）
2、& 和|  （反过来的分配律也是符合的）
3、^和&　（思考它和模2加、模2乘的类似之处）（(a^b)&c = (a&c)^(b&c)）
4、复数的加法和乘法 （元素是复数的矩阵被叫做复矩阵，它具有许多实数矩阵所具有的性质，其原因的本质就是复数的加法和乘法符合许多实数加法和乘法所符合的性质）
5、矩阵的加法和乘法 （思考分块矩阵的乘法计算公式，是不是和这个性质有一定关联之处呢？参考第五题中求矩阵等比数列的过程）
6、许多类似的计算复杂数学对象中的加法和乘法，比如三元数等
7、整数的模加和模乘，还包括整数矩阵的模加和模乘。（回想为什么我们可以简单的把加法和乘法变成模加和模乘来解决前面的所有问题）
8、任何可能的、新定义的，符合以上定律的运算符。（回想第七题，如果不理解成模2乘，是否也可以理解成一个全新的运算符）

也就是说，所有这一类问题中的加法和乘法，只要符合以上定律，并且存在线性递推关系（也就是那个能写成B'[i] = B[0]*A[0][i] + B[1]*A[1][i]...这样的式子），那么，我们就可以用矩阵来解决这个问题。

至此为止，矩阵这一强大的工具的第一个基本功能：计算线性递推关系已经介绍完了，您理解了多少呢？

2008/5/5 天地之灵 <tdzl...@gmail.com>:

8、再来一题，让你们知道矩阵不仅仅是矩阵，它不是一个人在战斗！
有一种k-电路矩阵，它有k个输入和k个输出，输入和输出都只有两种状态：高电位或低电位，输出和输出布成一个k*k的二极管矩阵，电子二极管的状态可
以通过激光设置，也具有两种状态：通过与不通过。
换言之，每个输出和输入当中的某些相通。如果所有与它连通的输入中存在一个高电位，那么输出为高电位。如果所有与它连通的输入全部为低电位，则输出低电
位。
现在，将N块相通k-电路矩阵一个接一个拼接成一串，每块电路的输入按照顺序连接到下一块电路板上。
现在，给定k个输入源的输入状态，求出最终一块电路板的k个输出的状态。
k不超过100，而N不超过2的32次方。

[鋆邓]

纠正一个错误,这里不能用k^2.81*N的算法,因为|不存在逆运算。我们只能选用k^3*N的算法

2008/5/25 鋆邓 <tdzl...@gmail.com>:

[鋆邓]

第九题：只要你有一定的数学基础，并且愿意把这个问题想象成一个数学题目，这个问题就相当简单了。
1、每个编号，在轮到它的约数的时候被改变一次状态
2、最终状态不变的，其约数个数是偶数个。否则其约数个数是奇数个
3、如果a是b的约数，那么b/a是一个整数，并且这个数也是b的约数。
4、如果{a}是一个递增序列，那么{b/a}是一个递减序列，并且在中间交汇。
5、当存在a == b/a时，b有奇数个约数。否则，其约数成对出现，必有偶数个约数（即：对于任意a<sqrt(b)，有a和b/a同为b的约数。若b有奇数个约数，必有sqrt(b)为整数并为b的约数。其中sqrt(b)表示b的平方根。）
6、换言之：若b为完全平方数，则其有奇数个约数。否则，其有偶数个约数。
7、换言之，N以内有多少个完全平方数，最终就有多少盏灯亮着，答案为floor(sqrt(N))
其中floor为求解小于等于一个实数的最大整数。

[鋆邓]

第10题，和上一题一样，你必须愿意把它当作一个数学问题。
以下摘自我以前写的解题报告：

定理1：当第一张牌(牌1)回到初始位置时，所有的牌都回到了初始位置。

证明：设有一次操作，某牌在操作前处于位置r(1<=r<=2*N)，那么，操作后，如果r原来属于前一半，显然r'=r*2; 否则，r'=(r-n)*2-1，即r'='r*2-(N*2+1);
将两个式子综合，可以得到r'= (r*2)%(N*2+1);
根据同余定理之一 ((i%m)*j)%m=(i*j)%m，可以整理出公式：i次操作后，该牌的位置为：
(r*(2^i))%(N*2+1);其中^表示乘方。
现在，我们假设经过M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1时，再次应用同余定理，可以证明对于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻译成自然语言就是：当第一张牌回到初始位置时，所有的牌都回到了初始位置。命题得证。

定理2：一定存在某次操作M（M<=2N），这次操作后，所有的牌都回到了初始位置。
证明：我们已经证明了牌1回到初始位置时，所有的牌都回到初始位置，所以我们只需要证明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整数解。证明这个定理前我们首先证明这样一个定理：
定理2.1：(2*r)%(2*n+1)==t
当t确定为1到2*n中的某值时(1<t<=2*n)，r在1到2*n间有唯一解
因为2*n+1是奇数，我们只要看一下就会发现r到t是一个一一映射，当t为偶数时，显然r=t/2，当t为奇数时，r=(t+1)/2+n，

现在我们来证明定理2。运用反证法，若牌1永远不能回到初始位置，根据鸽笼定理，牌1必然陷入了某个不包含位置1的循环，因为下一状态仅和当前状态有关，当前状态最多只有2*N种，所以显然一定在不超过2*N+1次操作内出现重复状态。而重复状态则意味着循环。
因为我们假设这一循环不包括位置1，我们设f(i)为循环中某状态，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)为若干次循环后出现的重复状态，即f(i)=f(j)。因为循环一直持续，不妨假设j>i+i。又因为循环不包括状态1，即对于任意的k>=i，f(k)!=1
根据定理2.1，我们可以根据当前状态推出上一状态，换句话说，若f(i)=f(j)，则f(i-1)=f(j-1)。继续套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假设j>i+i，即j-i>i，与另一假设对于任意的k>=i，f(k)!=1矛盾。
因此，可以证明，牌1所陷入的循环，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始状态。而且显然的，初始状态就是这循环中的一个状态。因此，牌1必然在一次循环后回到初始位置。另外，该循环必然不超过2*N次操作，因此，算法复杂度不超过O(N)（大O忽略常系数）

[pongba]

邓兄，将帖子置顶了:-)
这么多的解题报告，密集度太高，得慢慢消化:-D

2008/5/25 鋆邓 <tdzl...@gmail.com>:

2008/5/5 天地之灵 <tdzl...@gmail.com>:

矩阵也疯狂（天地之灵收集整理）

这个范围使你的计算机不能模拟整个过程了，所以----思考新的算法吧。

10、第二道调剂的题目：
有2N张牌，编号从1到2N，现在开始洗牌，每次将牌从中间分成两堆，将前一半依次插入偶数位置，后一半依次插入奇数位置
比如N = 3时，一次操作后得到：
1 2 3 4 5 6
4 1 5 2 6 3
接下来继续这个操作，得到
2 4 6 1 3 5
1 2 3 4 5 6
我们会看到3次操作之后，所有的牌回到了原来位置。
现在，请你用一个期望复杂度在O(N)以内的算法，对于给定的N，求出多少次洗牌操作之后，所有的牌都回到了原来的位置。
并且，请尝试证明一下你的复杂度在O(N)以内。

[pongba]

2008/5/10 鋆邓 <tdzl...@gmail.com>:

1、
我们分析 F(N) = F(N-1)+F(N-2)，这是一个显然的线性递推问题。
如果我们将F(N)和F(N-1)组成向量A(n) =( F(N), F(N-1) )
那么就有
F(N+1) = 1* F(N) + 1*F(N-1)
F(N)     = 1*F(N)  + 0*F(N-1)
A(n+1) = ( F(N)+F(N-1), F(N) )
= A(n) *B

其中B = 1 1
             1 0

那么，设A(0) = (F(1), F(0))
则有A(N) = A(0) * B^N
F(N) = (A(0) * B^N) [1]　　（其中[1]指取出该向量的第二项，这里用了C语言的思维理解向量和矩阵）
     = F(1) * ((B^N)[1][0] + F(0) * ((B^N)[1][1])
对于求B^N，我们有lgN的算法来求矩阵的幂。并且，整个运算过程中没有减法和除法，因此我们可以在运算过程中将所有的加法当作模加来计算，所有乘法当作模乘来计算。

这个方法，本来我以为只是一个技巧，利用矩阵运算的性质来降低复杂度。
但今天又看了一眼，发现实际上蕴含着一个更本质的思想：

原始的计算fib序列的算法是O(N)的，每一步都将fn-1, fn存起来，用于计算fn+1，这样做的原因是很显然的：fn+1只依赖于fn-1, fn；并且通过save这两个子问题的解，达到了避免重复计算的效果。然而，lgN的算法的存在昭示着这个算法里面必然还有可优化的成分（虽然看上去没有）。于是我仔细再思考了一下朴素的优化算法的过程，可以这样表示：

(f0, f1) => (f1, f2) => (f2, f3) => (f3, f4) => (f4, f5) => ..

借助于矩阵的优化算法，实际上将另一个额外的东西存了起来：即从(fk, fk+1) => ... => (fr, fr+1) 这个过程中发生的线性变换！（以矩阵表示）。事实上，从(f0, f1)=>..=> (f4, f5) 的线性变换（B^4），与从(f4, f5) =>..=>(f8, f9)的线性变换（B^4）是完全一样的。

这就是问题的复杂度能够借助矩阵来降低的本质原因：即，从(f0, f1) =>..=>(fn, fn+1)的线性变换能够归约为两个完全一样的子问题——从(f0,f1)=>..=>(fn/2, fn/2+1)的线性变换和从(fn/2, fn/2+1) =>..=>(fn, fn+1))的线性变换（它们都是B^4）。此外，线性变换是完全独立于，或者说是不依赖於被变换的变量（即(fk,fk+1)）的，所以对它们的计算也是完全独立的。所以实际上，fib序列计算是一个问题，fib序列计算中的线性变换的计算则是另一个独立的问题，两者都具有子问题结构。

一个明显的推广是这种优化方法不仅对于fib序列适用，对于任何满足f[n] = sigma(c[i]*f[i]);（ i = 0..n-1，其中c[i]是常系数）的序列都是适用的。

还有其它推广吗？

[鋆邓]

还有很多运用这种方法的场合，参见后面各题的解题报告。
至于你说的f[n] = sigma(c[i]*f[i])，对于c[i]不是很规律，并且无限的话，反而无法运用矩阵方法来解
矩阵所能解的是有限线性递推式问题。
对于无限的，比如说：每一个数是之前"所有"数的和，加上之前一个数的两倍，
那么针对f(n)是无法列出有限线性递推式的，但引入s(n)=sigma(f(n))，可以有：
s(n) = s(n-1)+f(n)
f(n) = s(n-1) + 2*f(n-1)
这样得到一个有限的递推式，才可以用矩阵来解决。

2008/5/25 pongba <pon...@gmail.com>:

[pongba]

2008/5/25 鋆邓 <tdzl...@gmail.com>:

还有很多运用这种方法的场合，参见后面各题的解题报告。
至于你说的f[n] = sigma(c[i]*f[i])，对于c[i]不是很规律，并且无限的话，反而无法运用矩阵方法来解
矩阵所能解的是有限线性递推式问题。
对于无限的，比如说：每一个数是之前"所有"数的和，加上之前一个数的两倍，
那么针对f(n)是无法列出有限线性递推式的，但引入s(n)=sigma(f(n))，可以有：
s(n) = s(n-1)+f(n)
f(n) = s(n-1) + 2*f(n-1)
这样得到一个有限的递推式，才可以用矩阵来解决。

 

嗯，很有意思:)

[rmq]

邓兄，你怎么这么厉害啊，我都仰慕的不行了！！！！

[pongba]

2008/5/25 rmq <zhan...@gmail.com>:

邓兄，你怎么这么厉害啊，我都仰慕的不行了！！！！

rmq也来了,欢迎哈:-)

[rmq]

潜水好久，一直在关注这个帖子 ~~
我也是 c++的罗浮宫 里的潜水员 haha

On 5月26日, 上午10时38分, pongba <pon...@gmail.com> wrote:
> 2008/5/25 rmq <zhangf...@gmail.com>:

[dailiangren]

定理二可以由数论中的欧拉定理得到。

On May 25, 2:51 pm, "鋆邓" <tdzl2...@gmail.com> wrote:
> 第10题，和上一题一样，你必须愿意把它当作一个数学问题。
> 以下摘自我以前写的解题报告：
>
> 定理1：当第一张牌(牌1)回到初始位置时，所有的牌都回到了初始位置。
>
> 证明：设有一次操作，某牌在操作前处于位置r(1<=r<=2*N)，那么，操作后，如果r原来属于前一半，显然r'=r*2;
> 否则，r'=(r-n)*2-1，即r'='r*2-(N*2+1);
> 将两个式子综合，可以得到r'= (r*2)%(N*2+1);
> 根据同余定理之一 ((i%m)*j)%m=(i*j)%m，可以整理出公式：i次操作后，该牌的位置为：
> (r*(2^i))%(N*2+1);其中^表示乘方。
> 现在，我们假设经过M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1时，再次应用同余定理，可以证明对于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻译成自然语言就是：当第一张牌回到初始位置时，所有的牌都回到了初始位置。命题得证。
>
> 定理2：一定存在某次操作M（M<=2N），这次操作后，所有的牌都回到了初始位置。
> 证明：我们已经证明了牌1回到初始位置时，所有的牌都回到初始位置，所以我们只需要证明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整数解。证明这个定理前我们首先证明这样一个定理：
> 定理2.1：(2*r)%(2*n+1)==t
> 当t确定为1到2*n中的某值时(1<t<=2*n)，r在1到2*n间有唯一解
> 因为2*n+1是奇数，我们只要看一下就会发现r到t是一个一一映射，当t为偶数时，显然r=t/2，当t为奇数时，r=(t+1)/2+n，
>
> 现在我们来证明定理2。运用反证法，若牌1永远不能回到初始位置，根据鸽笼定理，牌1必然陷入了某个不包含位置1的循环，因为下一状态仅和当前状态有关，当前状态最多只有2*N种，所以显然一定在不超过2*N+1次操作内出现重复状态。而重复状态则意味着循环。
> 因为我们假设这一循环不包括位置1，我们设f(i)为循环中某状态，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)为若干次循环后出现的重复状态，即f(i)=f(j)。因为循环一直持续，不妨假设j>i+i。又因为循环不包括状态1，即对于任意的k>=i，f(k)!=1
> 根据定理2.1，我们可以根据当前状态推出上一状态，换句话说，若f(i)=f(j)，则f(i-1)=f(j-1)。继续套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假设j>i+i，即j-i>i，与另一假设对于任意的k>=i，f(k)!=1矛盾。
> 因此，可以证明，牌1所陷入的循环，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始状态。而且显然的，初始状态就是这循环中的一个状态。因此，牌1必然在一次循环后回到初始位置。另外，该循环必然不超过2*N次操作，因此，算法复杂度不超过O(N)（大O忽略常系数）
>

> 2008/5/5 天地之灵 <tdzl2...@gmail.com>:

[hayate]

我们都知道fib数列有个通项

f(n) = c(a^n - b^n),  a和b是方程x^2 = x + 1的两个根。这个式子正好说明了fib数列有O(logn)的解法，因为就是乘方计算嘛。所以理想情况下(不考虑无理数的局限性)，这个式子的复杂度是很明显的。

 

实际上，这个式子应该叫做线性差分方程，比如

a(n) = sigma(c(i)a(i)) + b, b是常数，这种形式的方程总可以得到某种通项形式，也可以写成矩阵形式的。

 

还有个有趣的联系就是，如果观察矩阵B = 1 1
                                                              1 0

那么矩阵的特征方程正好是x^2 = x + 1，所以也叫做差分方程的特征方程。它可以简单的由f(n)改写成x^n得到。

2008/5/25 pongba <pon...@gmail.com>:

[hayate]

:) 看了这题，忍不住想说，群论真好。

2008/5/28 dailiangren <daili...@gmail.com>:

[Googol Lee]

恩，确实，光潜着就受益颇丰

就是插不上嘴……

2008/5/29 hayate <haya...@gmail.com>:

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[Googol Lee]

恩，确实，光潜着就受益颇丰

就是插不上嘴……

2008/5/29 hayate <haya...@gmail.com>:

--

[Justin L]

第一题，我的一个思路：
目的是要求数列第n项模M的值。因为第n项是递推的，我可以把从第一项到第n-1项的每一项均取模，再一项一项的往后推，推到第n项。其值和第n项取模
的值是相等的。
上面是思考过程。
这样操作的结果是，得到一个新的数列，其实就是对原数列每项均对M取摸。
这样我们就会发现，这个数列是在某项开始是循环的，不是0，就是一个x（x的值跟跟M有关，当然和f(0),f(1)也有些关系）。 0 x 0 x
0 x 0 ...




On 5月5日, 下午10时00分, pongba <pon...@gmail.com> wrote:
> 2008/5/5 鋆邓 <tdzl2...@gmail.com>:
>
> > 两项都很大，min一下也小不了。
>
> 我想说的是,只要m给定,无论n如何增长,都能在常数时间内计算出来.这已经比平凡的求法好多啦.
> 不过你应该是说还有更简单的,看样子m这个纬度上的复杂度应该不是O(m)就是O(1).O(1)的话等于就是能够有解析表达式了,不大可能啊.怎么降到O(m)是个问题.

[鋆邓]

楼上的结果是错误的.

比如m=3，f(0)=0 f(1)=1 结果是

0 1 1 2 0 2 2 1

的循环，而不是0 x 0 x的循环。

2008/6/1 Justin L <ice...@gmail.com>:

[Justin L]

呵呵，对，我错了。

其实应该这么说 0 x [其他数].... 0 x [其他数]....的循环。
这个0x中间的长度是有规律可找的，找这个规律比循环整个n要容易一些。只要能发现0x就行。

On Jun 4, 2:54 pm, "鋆邓" <tdzl2...@gmail.com> wrote:
> 楼上的结果是错误的.
> 比如m=3，f(0)=0 f(1)=1 结果是
> 0 1 1 2 0 2 2 1
> 的循环，而不是0 x 0 x的循环。
>

> 2008/6/1 Justin L <icer...@gmail.com>:

[ZelluX]

第一题难道不是用矩阵？只是中间结果每次都除m取余
复杂度 O(lgn)

> 1 1
> 1 2 1

[ccp...@gmail.com]

顶上了，同余+线性代数
就是运用矩阵O(logN)的。
0 1
1 1
这样的矩阵乘法得来的