codeforce 17D Notepad
这题实际求的是\(a^b\ mod\ n\),但是\(gcd(a,n)\)[下面记作(a,n)]不一定等于1.......
(a,n)等于1时直接费马小定理能推倒...
(a,n)不为1时,有如下事实(当然互素时显然成立):
\[a^{2\phi (n)}\ mod\ n = a^{\phi (n)}\ mod\ n\]
即
\[a^{\phi (n)}(a^{\phi(n)}-1)\ mod \ n =0\]
简单证明如下:
1.如果\(a^{\phi (n)}\ mod \ n =0\),等式显然成立.
2.否则,命题等价于
\[\frac{a^{\phi (n)} }{(a^{\phi (n)},n)} (a^{\phi (n)}-1) \ mod \ \frac{n}{(a^{\phi (n)} ,n)} = 0\]
即:
\[a^{\phi (n)}\ mod \ \frac{n}{(a^{\phi (n)} ,n)} = 1\]
到这里就能使用费马小定理了~
回到题目上:\(a^b\ mod\ n\)$实际上分两种情况:
1.\(b<\phi (n)\),此时直接算
2.else,\(a^b\ mod\ n=a^{b\ mod\ \phi (n)+\phi (n)}\ mod\ n\)
对任意(?)a,n成立
矩阵乘法结果的检验---Freivalds' algorithm
逛Uva的时候,看到了一个题,模型很简单,让验证一个矩阵是不是另一个矩阵的平方...朴素O(n^3)果断超时;看题解,原来是个随机算法-.-,思想和米勒拉宾素性测试很像,http://en.wikipedia.org/wiki/Freivalds'_algorithm
算法基于这么个事实:设X是一个随机向量,xi在{0,1,2...t}中任意选取;那么对于不同的矩阵A,B ,AX=BX的概率最多只有1/(t+1)
不严谨的证一下...
如果A != B ,而AX == BX 那必然有 (A-B)X==0 , 且 H=A-B != 0 ...
最坏情况呢...就是H的没个行向量都一样...就记为 h 吧, 既然非零,总有个hi != 0的
h1*x1+h2*x2+...+hn*xn==0 ==> xi=(h1*x1+...hi-1*xi-1+hi+1*xi+1+...hn*xn)/(-hi)
xi是0~t随机选的,他刚好满足这个条件的概率就是1/(t+1)...
那矩阵来乘个列向量,撑死是O(n^2)...做上几次测试,几乎就是必然了...更不必说那个1/(t+1)是个上界...
codeforce 111D Petya and Coloring
公式都化出来的,居然还要对着数据调了半天....囧
题意大概是:给你一个n*m的棋盘和k种颜色,求满足要求的涂色方案,额...要求就是:垂直方向把棋盘分成两边(非空),不管怎么分,两边的颜色种数相等....
满足要求的方案首先要最左最右的满足颜色数相等,然后中间,在最左和最右边的交集中随意取;
最后化出来就是:
t1=min(m,k),t2=min(m-i,(k-i)/2);
这个F(x)表示x种颜色填到n个格子里,每种至少一个,有多少种涂法:
F(1)=1,F(x)=x^n-F(x-1)-F(x-2)-...-F(1);
eclipse debug问题
初学java,用eclipse调试时,它给我弹出这玩意:
上网查,有人说是"From this (http://forum.java.sun.com/thread.jspa?threadID=618145) it seems that Eclipse is trying to connect to your external IP instead of localhost." 原文:http://forums.fedoraforum.org/archive/index.php/t-97415.html
于是在/etc/hosts里加了句127.0.0.1 localhost
问题解决了
hud4048
核武的思路:http://hi.baidu.com/aekdycoin/blog/item/69e075f5e200bcf47709d769.html
参考完核武报告,没完全懂~翻了翻组合数学书,这实质上就是求元素可重复的圆排列--许多组合数学书里讲莫比乌斯反演时唯一的例题~
先求 r 种不同元素,放在圆的n个点上 , 有几种放法, 旋转后相同算一种.
做法是:设周期为为d,d|n,的方案数是Td(r) 则 每个这样的圆排列,对应着d个线排列
线排列总数是r^n,所以:
莫比乌斯反演后:
总的方案数M_n就是各种周期的和:
因 d|k|n , 设k'=k/d . n'=n/d
注意到后面一部分和等于n'的欧拉函数,故Mn可以写成:
问题基本解决,剩下就是核武报告里说差不多,把最小公约数是i的倍数的方法数求出,容斥原理搞搞.
最后的答案应该是:
其中r_n表示重量是n的倍数的石子种数
mu(n) 和 phi(n) 都可以在预处理时筛出来,
n的分解只需要搞一遍就够了~
遗憾的是,还是很慢,board的第一名时空复杂度都比我写的好~ym
catalan number~卡塔兰数\卡特兰数...
http://en.wikipedia.org/wiki/Catalan_number
catalan数的身世,wiki(上面链接)有....那里还提供了5种(?)求法~第一种:母函数,第二种:全体数-非法数,第三种:通过定义一个叫exceedance的玩意,然后通过一个很奇葩的构造,说明exceedance等于0,1,2...n的路径数相等,直接得出结果~第四种是基于卡特兰数在多边形的三角划分的,推出个递推式~第五种是根据递推式,死推~
昨天,上海网赛热身,那题http://acm.hdu.edu.cn/showproblem.php?pid=4015, 是一个很像很像catalan数的玩意~大概是:给你两种数,a,b,权值分别是1和-m , a有k*m+1个,m有k个 , 问有几种排列方法,使得前任意项的和都不为0;
m取1时,就是红果果的catalan数~
m!=1时 ~ 不会..不过又找到了卡特兰数一个牛B的不同于wiki那5种的求法,完全兼容上面那题~这是本文存在的原因~
原文在这里,里面还有好几种别的求法:谷歌文档~偷来了,怕丟不好意思
现在 说说那个求法:
给你n+1个'/'和n个'\' , 让你用这些随意的首尾相接组到一起, 一共就C(2n+1,n)种组法,我们要求的是除起点外所有点的海拔都大于0的组合数;
每种(含非法)组法就称为一个pattern , 显然这些pattern有一个性质,最后那点比第一点高出一个单位;
还有一个不那么显然的性质:在连接最后一点和第一点的直线上,没有一个\或/的端点落在上面,这是因为最后那点才是1,落在上面就意味着有分数,这不可能;
高潮来了~现在把两个相同的pattern首位相接,从前面不同的2n+1位开始的2n+1位,一共有2n+1个不同(why?我再想想)的pattern:其中,只有一个是合法的!!!(想象一条斜率为1/(2n+1)的直线从底部缓缓升起)
so~总的合法序列就C(2n+1,n)/(2n+1)个~
用这个来做上面的那道题,没压力啊,连化简都省了,直接出结果啊!~~~
SPOJ3871 GCDEX
这题的描述对我这种语言能力残缺的人来说,复述起来太难:
,然后累加一下...额累加时第i项还要减个i~
个~这意味着:
;现在证明,T(n)是一个积性函数
证明:
设 m , n 满足 (m,n)=1:
则:
由于(m,n)=1,故dn与dm互素,所有dn,dm的组合正好取遍mn的约数
到了这里,只需考虑n等于素数的幂时T(n)的值:
根据T(n)的定义,显然有:
有了这个性质,就有可以在O(n)时间内用这个 牛X的筛法 把表打出来,然后求和还是O(n),查询什么的显然O(1)咯lol...
代码:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define FF(i,b) for(i=0;i<(b);i++)
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ZERO(x) do{memset(x,0,sizeof(x));}while(0)
#define SWAP(a,b) do{int _tmp=a;a=b;b=_tmp;}while(0)
#define INFI 2000000000
#define INFF 1e100
#define maxn 1000000
typedef long long LL;
int p[maxn+1],ph[maxn+1],pk[maxn+1],T[maxn+1];
LL G[maxn+1];
void sevie()
{
memset(p,0,sizeof(p));
int i,j;
p[0]=ph[0]=0;ph[1]=1;T[1]=1;
for(i=2;i<=maxn;i++)
{
if(!p[i]){p[++p[0]]=i;ph[i]=i-1;pk[i]=i;T[i]=(i<<1)-1;}
for(j=1;p[j]<=maxn/i;j++)
{
p[p[j]*i]=1;
if(i%p[j]){
ph[i*p[j]]=ph[i]*p[j];
pk[i*p[j]]=p[j];
T[i*p[j]]=T[i]*T[p[j]];
}
else{
ph[i*p[j]]=ph[i]*p[j];
pk[i*p[j]]=pk[i]*p[j];
if(i==pk[i])T[i*p[j]]=p[j]*T[i]+ph[i*p[j]];
else T[i*p[j]]=T[i/pk[i]]*T[pk[i]*p[j]];
break;
}
}
}
G[0]=0;
for(i=1;i<=maxn;i++)G[i]=G[i-1]+T[i]-i;
}
int main ( int argc, char *argv[] )
{
sevie();
int n;
while(scanf("%d",&n)!=EOF)
{
if(!n)break;
printf("%lld\n",G[n]);
}
return EXIT_SUCCESS;
}
Z2上高斯消元求秩
//Z2上高斯消元求秩,用位压缩储存
int rank(long long a[],int n)
{
int i,j;
for(i=0;i<63;i++)
{
int mask=1<<i;
for(j=i;j<n;j++)if(a[j]&mask){swap(a[i],a[j]);break;}
for(j++;j<n;j++)if(a[j]&mask)a[j]^=a[i];
}
for(i=j=0;i<n;i++)if(a[i])j++;
return j;
}
dhclient.conf
貌似 dhclient-4.2.0-21.P2.fc14-x86_64 默认的 dhclinet.conf 在 /etc/dhcp/里，要手动创建
自己写的split函数
int split(char *text,char *x,char **output)
{
int textlen,xlen,//后面初始化
pointer=0,//"text"的偏移
n=0;//output的个数
textlen=strlen(text);
xlen=strlen(x);
while(1)
{
char *p, *t;
p=strstr(text+pointer,x);
if(NULL!=p)*p=0;
t=(char *)malloc(sizeof(char)*strlen(text+pointer)+4);
strcpy(t,text+pointer);
output[n++]=t;
pointer=p+xlen-text;
if(NULL==p)break;
}
return n;
}