1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | |
快速傅里叶变换计算大整数乘法
我们知道，两个 N 位数字的整数的乘法，如果使用常规的算法，时间复杂度是 O(N2)。
然而，使用快速傅里叶变换，时间复杂度可以降低到 O(N logN loglogN)。
假设我们要计算以下两个 N 位数字的乘积：
1 2 | |
将上面两个式子相乘，得到以下公式 (共 2N - 1 项)：
1
| |
非常容易验证，上式中的 ck ( 0 ≤ k ≤ 2N-2 ) 满足以下公式：
1
| |
上式共有 N 项，ai 和 bj 的下标 i 和 j 满足 i + j = k。若不满足 0 ≤ i, j ≤ N-1 时，则令 ai = bj = 0。
我们以两个 3 ( N = 3 ) 位数 a = 678 和 b = 432 的乘积来说明以上过程吧。
1 2 | |
由此：
1 2 3 4 5 | |
最后：
1 2 3 | |
如果按以上方法计算大整数的乘法，时间复杂度是 O(N2)。
但是，我们注意到，向量 {ck} 是向量 {ai} 和向量 {bj} 的卷积。
根据卷积定理，向量卷积的离散傅里叶变换是向量离散傅里叶变换的乘积。于是，我们可以按照以下步骤来计算大整数乘法：
分别求出向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj}。将 {Ai} 和 {Bj} 逐项相乘得到向量 {Ck}。对 {Ck} 求离散傅里叶逆变换，得到的向量 {ck} 就是向量 {ai} 和向量 {bj} 的卷积。对的向量 {ck} 进行适当的进位就得到了大整数 a 和 b 的乘积 c。
对于复数向量 { xN-1, …, x1, x0 }，离散傅里叶变换公式为：
离散傅里叶逆变换公式为：
注意到离散傅里叶逆变换除了指数的符号相反以及结果需要乘以归一化因子 1/N 外，与离散傅里叶变换是相同的。所以计算离散傅里叶变换的程序稍做修改也可以用于计算逆变换。
在我们的例子中，乘积 c = 292896，共 6 位数字，N 需要扩展到 23 = 8。那么，向量 {ai} 和向量 {bj} 如下所示：
1 2 | |
为了求出以上向量的离散傅里叶变换，我们令
1
| |
为了方便计算，我们预先求出 ω 的各次方，如下：
1 2 3 4 5 6 7 8 | |
注意到当 n > 2 时，an = 0，于是：
1 2 3 4 5 6 7 8 | |
同样，当 n > 2 时，bn = 0，于是：
1 2 3 4 5 6 7 8 | |
这样，向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj} 如下所示：
1 2 | |
现在，将她们逐项相乘得到向量 {Ck}，即
1
| |
为了求出向量 {Ck} 的离散傅里叶逆变换，我们令
1
| |
为了方便计算，我们预先求出 ω 的各次方(注意 ωk+8 = ωk)，如下：
1 2 3 4 5 6 7 8 | |
于是：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | |
这样，我们就使用离散傅里叶变换和逆变换计算出了向量 {ai} 和向量 {bj} 的卷积向量 {ck}，如下所示：
1
| |
这和我们在前面直接使用向量 {ai} 和向量 {bj} 来计算卷积的结果是一样的。
但是，这个算法的时间复杂度还是 O(N2)。我们绕了这么一大圈，不是白费劲了吗？
现在就到了关键时刻
关键在于：直接进行离散傅里叶变换的计算复杂度是 O(N2)。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要 O(N logN) 的计算复杂度。 N logN 和 N2 之间的差别是巨大的。例如，当 N = 106 时，在一个每秒运算百万次的计算机上，粗略地说，它们之间就是占用 30 秒 CPU 时间和两星期 CPU 时间的差别。
快速傅里叶变换的要点如下：
一个界长为 N 的离散傅里叶变换可以重新写成两个界长各为 N/2 的离散傅里叶变换之和。其中一个变换由原来 N 个点中的偶数点构成，另一个变换由奇数点构成。这个过程可以递归地进行下去，直到我们将全部数据细分为界长为 1 的变换。什么是界长为 1 的傅里叶变换呢？它正是把一个输入值复制成它的一个输出值的恒等运算。要实现以上算法，最容易的情况是原始的 N 为 2 的整幂次项，如果数据集的界长不是 2 的幂次时，则可添上一些零值，直到 2 的下一幂次。在这个算法中，每递归一次需 N 阶运算，共需要 log N 次递归，所以快速傅里叶变换算法的时间复杂度是 O(N logN)。
由于快速傅里叶变换是采用了浮点运算，因此我们需要足够的精度，以使在出现舍入误差时，结果中每个组成部分的准确整数值仍是可辨认的。长度为 N 的 B 进制数可产生大到 B2N 阶的卷积分量。我们知道，双精度浮点数的尾数是 53 个二进位，所以：
2 x log2B + log2N + 几个 x log2log2N < 53
上式中左边最后一项是为了快速傅里叶变换的舍入误差。
所以，为了能够计算尽量大的整数，一般 B 不会取得太大。在计算机程序中经常使用 256 进制进行运算。但是如果经常需要将计算结果和十进制互相转换，则往往使用 100 进制进行运算。
快速傅里叶变换：
FFT算法设计的基本思想，就是充分利用DFT的周期性和对称性，减少重复的计算量；并把N点长序列分成几个短序列，减少每个序列长度，可大大减少计算量。
实践中使用最多的FFT是“基2”算法。
所谓“基2”，就是令DFT的点数N满足 
（5）
FFT基2算法分为时域抽取法（Decimation In Time）和频域抽取法（Decimation In Frequency）两大类。
本文重点介绍其中的时域抽取法快速傅里叶变换（DIT－FFT），算法设计思想要点如下：
1、把长度为N的时域序列x（n）按n的奇偶分为两组，变成两个序列，长度均为N/2。
即 
（6）
其中一个N/2点的DFT为 
（7）
另一个N/2点的DFT为 
（8）
2、不难推出原序列x（n）的N/2点DFT为 
（9）
注意：上式仅是X（k）的前一半即N/2点运算，整个N点DFT结果还要加上后一半计算。如果老老实实计算后一半N/2点DFT，则并没有减少任何计算量。但考虑可利用DFT及其变换因子的周期性和对称性，并利用前一半计算结果，后一半计算可表示为 
（10）
注意：
a->A, b->B C->c 用三次快速傅立叶变换。
ubuntu各种设置
1 2 | |
ubuntu 小键盘不能用
按下 shift + alt + NumLock 就好了
开机自动开启小键盘
1 2 3 4 5 6 7 8 9 10 | |
bash
修改sh默认连接到bash的一种方法：
1
| |
选择no即可.
intel集显驱动
1 2 3 | |
修改MTU值
其实网卡的MTU值是保存在/sys/class/net/eth0/mtu文件中，所以可以通过查看和修改文件达到修改MTU的目的：
以下以查看和修改eth0为例：
1 2 3 4 | |
修改屏幕亮度
挂起时是独显，恢复时是集显的话，屏幕亮度设置指向独显，导致不能设置。
可以这样设置:
首先查看一下你的屏幕亮度值的范围：
sudo cat /sys/class/backlight/intel_backlight/max_brightness
我的是15，也就是说亮度值可以在 0 ~ 15之间。
echo 3 > /sys/class/backlight/intel_backlight/brightness
Ubuntu 10.04 窗口关闭最大化最小化按钮位置调整
使用图形界面“gconf-editor”修改这个配置文件。
我们要修改的项目在“apps/metacity/general”这里。依次点击“+”号展开按钮，导航到“general”项。
在“general”项中找到“button_layout”条目，双击这个条目对它进行修改。
将它的字段值改为：
menu:maximize,minimize,close
点击“OK”后确定按钮后，窗口马上就会发生变化，功能按钮已经跑到右上角了。
找回Ubuntu 13.04 Nautilus 的 ’Backspace’键 的’返回’功能：
打开终端：
sudo gedit ~/.config/nautilus/accels'
在配置文件最下面加上：
(gtk_accel_path “
然后保存
接着重启Nautilus:
nautilus -q
新安装的ubuntu 13.04 在执行sudo apt-get update的时候总是显示
W: 无法下载 bzip2:/var/lib/apt/lists/partial/cn.archive.ubuntu.com_ubuntu_dists_raring-updates_main_binary-i386_Packages Hash 校验和不符
解决办法：
修改etc/apt/apt.conf.d/00aptitude
最后加一行: Acquire::CompressionTypes::Order “gz”;
sudo apt-get update
linux 访问 win 共享
smb://192.168.XX.XX/
火狐可以设置backspace键为后退或页面向上滚动
地址栏输入about:config
名称: browser.backspace_action
默认值: 2 (无作用)
修改值:
* 0 - 后退
* 1 - 页面向上滚动
增加右键命令：在终端中打开
软件中心：搜索nautilus-open-terminal安装
命令行：sudo apt-get install nautilus-open-terminal
重新加载文件管理器
nautilus -q
或注销再登录即要使用
更改工作区数量：
compiz->常规选项->桌面尺寸
或者
要更改行的数量，请键入以下命令，将最终数量更改成您希望的数字。按回车。
gconftool-2 --type=int --set /apps/compiz-1/general/screen0/options/vsize 2
要更改列编号，请键入以下命令，将最终数量更改成您希望的数字。按回车。
gconftool-2 --type=int --set /apps/compiz-1/general/screen0/options/hsize 2
替换indicator-me图标
/usr/share/icons/ubuntu-mono-dark/status/22/user-offline.svg
换成
/usr/share/adium/message-styles/ubuntu.AdiumMessageStyle/Contents/Resources/Incoming/buddy_icon.png
关蓝牙图标:用dconf-editor
com->canonical->indicator->bluetooth
panel设置:
org->gnome->gnome-panel->layout
org->gnome->desktop->wm->preferences
由于没有公钥，无法验证下列签名 ppa
W: GPG签名验证错误： http://ppa.launchpad.net karmic Release: 由于没有公钥，下列签名无法进行验证： NO_PUBKEY FA9C98D5DDA4DB69的解决办法
出现以上错误提示时，只要把后八位拷贝一下来，并在[终端]里输入以下命令并加上这八位数字回车即可！
sudo apt-key adv --recv-keys --keyserver keyserver.Ubuntu.com DDA4DB69
此类问题均可如此解决！
安装MATE桌面环境
1 2 3 4 5 6 7 8 9 | |
通知区域设置
打开终端输入：
1 2 3 | |
安装notify-osd界面配置软件
1 2 3 | |
找到NotifyOSD配置工具
The configuration dialog should be in Applications->Accessories. There’s a setting for notification duration.
改变通知区域位置在终端输入
1 2 3 4 5 6 7 | |
系统启动服务设置
首先是安装
1
| |
然后在终端 sudo sysv-rc-conf
快捷键
Ctrl+Z 把当前进程送到后台处理。fg 返回
Ctrl+Alt+F1 切换到第一个文本终端。在Linux下你可以有多达六个不同的终端。
Ctrl+Alt+F7 切换到第一个图形用户界面（一般来说X-window在第七个终端）
Ctrl+Alt+L 锁屏
Ctrl+Alt+→/← 在不同工作台间切换
彻底删除 XXX
1
| |
ibus不起动 或 界面显示英文
在登录界面下方选择"汉语"
静态IP、DNS的设置
设置IP
sudo gedit /etc/network/interfaces
1 2 3 4 5 6 7 | |
修改DNS
sudo gedit /etc/resolv.conf
1
| |
TopCoder 规则入门
进入Options->Editor，在这里添加新的编辑器。编辑器的名字，比如KawigiEdit；在EntryPoint一栏输入jar的运行方式，这里是：kawigi.KawigiEdit；ClassPath就是类所在的位置，这里通过Browse按钮将KawigiEdit.jar的地址添加进来，比如C:\Documents and Settings\Administrator\桌面\topcoder\KawigiEdit.jar
ubuntu10.04运行客户端：
下载更新点的icedtea-netx及其依赖安装 http://packages.ubuntu.com/zh-cn/precise-updates/icedtea-netx
基本规则
TopCoder的比赛类型很多，最常见的是周赛SRM（Single Round Match），另外还有TCHS SRM（TopCoder High School SRM，题目和SRM一样，仅限中学生参加，参赛者水平较低，据说涨rating很容易），马拉松（Marathon Matchs），还有TCOpen（每年两次的大比赛）之类的比赛。因为大多数人都在做SRM，所以本文介绍的TC比赛即为SRM。
SRM的规则总结起来就是一句话：75分钟做完3道难度递增的题。
TC的每个用户（handle）都有自己的积分（rating），从0-3000+不等。成绩越好，分数越高。
积分与颜色的对应为：白色——未参赛（unrated）；灰色——0~899；绿色——900~1199；蓝色——1200~1499；黄色——1500~2199；红色——2200+。另外排名最高的几个人在TC客户端中会变成红色靶子图标。
比赛分为两个Division，Div I和Div II。白色灰色和绿色的参加Div II，蓝色黄色和红色的参加Div I。Div I的题要比Div II难许多，一般DivII的最后一题和Div I的第一或第二题是一样的。无论是Div I或Div II。三道题目的Score一般为250, 500和1000。 TC的计分规则很诡异，可以见 http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System ，但基本是没人看的懂。不过，TC积分规则的基本思想很简单。
首先是SRM每道题的计分规则。题目从打开开始计时，随着时间的流逝，你这道题目可能得到的分数也越来越少。不过分数减少的速率会逐渐变慢（有人说是先快后慢再快再慢，我不清楚到底哪个是对的，不过总体趋势是越来越慢），一般1000分的题目在降低到300分的时候就基本不会再下降太多了。每道题点击Submit才算正式提交，如果Submit之后发现错误，还可以再次点击Submit修改提交，不过这样会扣除这道题一定的分数。
其次是TC的计分规则。复杂的数学公式很难看懂，但大概的计分思想是：根据此次比赛的得分算出一个这次比赛的rank，然后和以前的rank做比较，求出一个期望的rank，再根据这个期望的rank调整rating。而有时也会出现考得很砸但依然涨rating的情况，不过总体来说TC的计分公式是十分稳定的。
运行环境
TC的客户端是一个Java程序，所以需要JRE（Java Runtime Environment）或者JDK（Java Development Kit）来运行。如果平时不写Java程序的话，装JRE就可以了。毕竟JDK比JRE大一个数量级，下载慢。安装照着提示完成就行了。推荐使用1.4.1以后的版本，因为带了java web start，可以快速登陆。具体方法下一部分讲。
JRE下载地址（中文）： http://www.java.com/zh_CN/download/index.jsp
注册
原文在注册的地方没有详细说明，但很多人似乎对注册都有疑问。所以这里我来注册一个小号，并通过整个过程讲解如何注册。
首先打开 http://www.topcoder.com/tc （本文后面TopCoder的主页都指这个网址），然后点击右上角的Register Now（没看到？你可能看到了一个Login，目光向下挪一点，那个红底白字的“Register Now”就在下面）。接下来会弹出 http://www.topcoder.com/reg 这个页面，因为我们要参加SRM，所以选择第一个，Competition Registration。如果要参加TCHS可以选择第二个High School (Secondary School) Registration。这些以后都可以更改（这里没有选的如果以后要选上，只需要更新个人设置并挑勾；如果选上的要撤销选择则需要点一个“Unregister”的链接）。这里选择项目的多少和后面的页面需要填写内容的多少相关，本文以只选择第一项为例。
需要填写的项目和对应的中文翻译如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | |
点Submit，进入Confirm页面，确认信息。如果有误可以点Edit修改，否则点最下面的Confirm提交。
接下来进入Success，提示你已经发送一封邮件到你的邮箱中，你必须去点击里面的链接激活用户。激活之后就可以使用这个用户了。
登录
登录的方法一般都是使用Java Web Start。
在TopCoder主页（http://www.topcoder.com/tc%EF%BC%89%E5%B7%A6%E4%BE%A7Algorithm (SRM)->Launch Arena（已失效：最下方有一段话，第一句是“Load the Arena as an Applet or as a Java Web Start Application”。点“Java Web Start Application”，）就会自动下载登陆需要的文件（一个jnlp格式的文件，本机装了JRE/JDK才能打开）。经测试在IE7下这个链接似乎不管用，在Firefox 3下正常。
然后运行下载下来的jnlp文件，就打开了TC客户端。第一次运行和有更新的时候会自动下载安装程序，等待即可，很快。
在我这里有时会提示“语法错误”，但没有任何影响，点“确定”就可以。启动可能会慢一些，耐心等待。
然后输入用户名密码，在Connection的地方选合适的登录方式（一般Direct就行，如果不行的话可以试试别的或者用AUTODETECT自动检测），在PROXY处设置代理，点GO登陆。这时可能还会提示语法错误，再确定就行，这个也没有什么影响。
界面
下面的图们来自原文，很经典，不打算改动了。请使用等宽字体浏览。
主界面：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
菜单项:
1 2 3 4 5 6 | |
Rating Key: handle的颜色是随着积分而改变的，这里显示了积分与颜色的关系。
MESSAGES: 比赛的时候这里有注册提示和clarification。
LEADER BOARD: 看每个room的最高分。
Who’s here: 当前room里的人。
Chat Area: 聊天。
练习
在Practice Rooms里随便选择一个room就可以进入practice了。
界面与主页面稍有变化，但基本相同，略去不画。主要的变化就是Who’s here分成了两块，多了一块Who’s assigned。这块显示的是谁被分到了这个room。因为是练习区，所以只要是在这里打开过题的都算是assigned。而在正式比赛中room是由TC分配的。这里显示的是被分配到这个room的人。界面上还有一个变化是Chat Area顶上多了三块。最左边的是一个下拉菜单。里面有三个分值，选择后就可以打开相应的题目。中间的summary可以看这个room里每个人的提交情况。
在practice room里只有coding phase。提交后要判的话需要自己选择Practice Options（多出来的菜单项）里的Run System Test。
比赛
每次比赛(除了1年两次的大赛)都需要在赛前3小时-5分钟之间登陆注册方可参加，注册需要在Active Contest菜单中，选择你要参加的那个比赛，再选择Register。注意比赛前5分钟注册停止，这时候如果没有注册就不能参赛了。而注册了没有打开题目也视为没有参赛，rating不变动。
然后TopCoder开始根据每个人的rating分配room，一般每个room都有高手和菜鸟，只不过如果你的rating高，和高手分在一起的概率高一些（当然也不一定是这样，比如我上次就和yuhch大牛分在了一起……）
分配完成后，Active Contest菜单中Register一项变成Enter。选择后可以直接进入你被分配到的room。Active Contest菜单最下面还有一项暗色背景的Room子菜单，可以进入各个room溜达。
进入自己room的时候一般离开始只有3分钟左右，静一下心就可以直接开始比赛了。coding phase的过程与practice基本相同。注意每题的得分是和用的时间相关（见前面的计分规则），而时间是从你打开该题开始算的。所以一题做完后可以不急着打开下一题，先放松一下。 75分钟的coding后是5分钟的intermission，这段时间是用来休息和聊天的。
然后就是最刺激的15分钟challenge phase，也就是通常说的cha人。打开summary，双击别人的各题Score可以打开那题的程序，如果觉得有错误就可以点左下的Challenge然后输入你认为他会错的输入数据，如果输入数据合法那么系统会用标程的输出和这个程序的输出对比，如果出现不同则cha人成功。成功的话你能得到50分，对方该题分数为0；而如果失败了，你会被减去25分。每个程序只能成功被cha一次，也就是说，如果有人cha掉了这个程序，你就不能再次cha。但是一个人可以cha某个程序很多次，直到这个程序被cha掉或者你放弃。
Challenge结束后就是System Test。这个过程一般比较慢，可以先走开做其他事，过20分钟再回来看结果。System Test中的测试数据有两种：一种是出题者准备的测试数据，一种是成功cha掉别人的数据。所以，TC中很少出现有bug的程序能通过System Test的情况。 结果出来后再过一段时间，就可以看到一系列message,比如rating更新了，新的practice room建好了以及可以通过主页查看这次比赛的数据了。这时比赛就宣告结束。
注意事项
1.在TC主页（http://www.topcoder.com/tc%EF%BC%89%E4%B8%8A%E5%8F%AF%E4%BB%A5%E7%9C%8B%E5%88%B0Next SRM，这是下次SRM的时间。注意我们的时间与他们刚好相差12小时，因此若时间是7月9日9:00 PM的话，这里是7月10日9:00 AM。还有要注意的是美国有夏令时，非夏令时的时候，还要再加1小时，就是7月10日10:00 AM。
2.Practice Rooms里写的程序只要点SAVE就可以保存，下次login的时候还可以看到，但是比赛时候的程序必须Submit才可以在coding phase结束后保存(coding phase结束前还是只要SAVE就可以的)。
3.若想cha别人的程序，自己必须是正分(0分也不行)，所以若没有一题有正确的程序但有很好的数据的话，随便交一道看上去正确的程序，然后在challenge的时候快下手，就可以赚到了。
4.客户端自带的编辑器只有基本的编辑功能和编译及测试功能，所以若觉得不方便的话可以使用parser和plugin，TC主页最下面有plugin的连接。每个plugin都有详细说明文档，这里不再赘述。
5.TC的FAQ： http://www.topcoder.com/?&t=support&c=index
6.最后一条，千万不要作弊，会有严重的后果。
SRM的输入输出
SRM是不用标准或文件输入和输出的，只要写一个类的一个成员函数。也就是说，你需要编写的并不是一个完整的程序，而是一个类。 输入是成员函数的参数，输出用return，所以经常需要STL中的vector和string。
因为TC的系统并不测试标准输出，所以标准输出可以当调试用。
编辑器
打开题目后，TC默认使用的编辑器为Standard，在右上角可以看到，choose your editor。我们可以通过使用插件的方式增加自己的编辑器。
随便进入一个Practise Rooms，可以看到增加了一栏为Tools，Tools下有个TopCoder Plugins，点击进入，或者通过这个链接：
http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
常用的编辑器有KawigiEdit、PopsEdit和FileEdit，其中KawigiEdit编辑器已经将运行sample的功能添加了进来，会比较方便一些。
以安装KawigiEdit为例说明下插件的安装方法。
a.下载KawigiEdit，从上面的页面链接或者是
http://www.topcoder.com/contest/classes/KawigiEdit/KawigiEdit.jar
下载放到一个目录中，比如：
C:\Documents and Settings\Administrator\桌面\topcoder
b.进入Options->Editor，在这里添加新的编辑器。点击Add按钮，在Name一栏输入编辑器的名字，比如KawigiEdit；在EntryPoint一栏输入jar的运行方式，这里是：kawigi.KawigiEdit；ClassPath就是类所在的位置，这里通过Browse按钮将KawigiEdit.jar的地址添加进来，比如C:\Documents and Settings\Administrator\桌面\topcoder\KawigiEdit.jar
c.将KawigiEdit设置为默认的编辑器，将Default复选框打勾
Java 多次排序的方法
Java 多次排序的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | |