C(6,4)^2

ride 有飞碟的意思

不想飞翔，不是因为没有翅膀，而是失去了梦想

远而望之，皎若太阳升朝霞；迫而察之，灼若芙蕖出渌波

含义：
远远望去，明亮得像初升的太阳，霞光万道；从近处细看，鲜丽得像渌波中的荷花，亭亭玉立。　　
这几句用比喻和烘托的手法来写洛神各种惊人的美丽，可用以形容女子美丽的容貌和娴静的身姿、神态。

配置Hadoop 官方 http://hadoop.apache.org/docs/r1.0.4/cn/quickstart.html
CSDN手把手教程，http://www.cnblogs.com/kinglau/p/3794433.html

Java 8, Oracle的是官方，OpenJDK是开源，但是不稳定

SSH安装 ssh localhost

里面遇到hadoop 用户没有访问 /usr/local/hadoop权限，需要root chmod

Firefox一直上网极其慢，baidu打不开，找了半天找到一个百度贴吧和我一样的情况，原来是14.04版本FF自带太老了，很多bug，需要更新，然后装chrome就可以直接google了

sogou拼音也装上了，虽然自己不喜欢update，但是有时候又是非常重要的

用Stirling 公式计算n! 的 多项式公式，这样可以计算log(n!)的渐进时间复杂度，也即算n! 的bit位数。

Wilson 定理给定的是素数判定的充要条件，但是用处不大，因为计算(n-1)!是爆炸增长的，实际意义不大。

1^k+2^k+….n^k k=1,2,3,4都有公式，因此是一个母函数(生成函数), 和 (n+1)^(k+1) 是一个时间复杂度

Posted by richard爱闹 - 3月 24 2015
如需转载，请注明： 本文来自 Richard

夫神提到CF一题sort 8W多个数据TLE，要Shuffle才能过。于是开始再次研究QSort

Arrays.sort 其实是Dual pivot QSort，作者戳 http://iaroslavski.narod.ru/

他做出的贡献是对于qsort里 swap的平均操作次数从nlogn降到了0.8nlogn，并给出证明 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf,

而compare次数不变，并且对于许多普通单pivot的QSort会最坏复杂度的情况， 该算法都不会出现最坏复杂度。

但是他的缺点依然是最坏ON^2没有避免。正如最后一个数据TLE一样。

没有看STL源码剖析一直是遗憾，老早的read list一直拖到现在，今天找到这篇博客 http://feihu.me/blog/2014/sgi-std-sort/#comment-1922883630

瞬间豁然开朗，其实解决方案就是混合sort，这也是我们没有纯粹原创方法的解决方案之一，heap sort既然常数因子比较大，而且没有利用局部性原理 http://www.zhihu.com/question/20842649

所以qsort多数情况比他快，但是QSort最坏n^2一直没有解决，那么何不综合二者有点呢，设置递归深度，如果达到一定深度，就heapsort。这是introsort最核心的算法。http://en.wikipedia.org/wiki/Introsort

但是谈到具体细节，还有很多值得推敲的，比如insertion sort怎么优化，快排怎么用while+一次递归调用来减少函数调用次数设置的递归深度阈值是2*lower_upper(logn),
因为平均是logn递归调用，最坏n，如何找到这之间的一个阈值也是一门学问，以及16个元素作为insertion和qsort之间的阈值，(dual pivot qsort 是17)

具体细节还看这篇饕餮盛宴！http://feihu.me/blog/2014/sgi-std-sort/#comment-1922883630

源码在stl_algo.h中

Posted by richard爱闹 - 3月 23 2015
如需转载，请注明： 本文来自 Richard

总结一下组合数DP公式
之前APAC Round2 ProA题，给定M种字符，问N个字符的排列有多少，其中每个字符至少1次。

f(m, n) 含义先往题意靠，m表示m种，n表示前n个位置，

f(m-1, n) 表示m-1种放在n个位置，这个显然不行，因为没有放满m种字符，
f(m, n-1) 表示m种放在前n-1个位置，那么最后一个位置任意放一种，m*f(m, n-1)
f(m-1, n-1) 表示m-1种放在前n-1个位置，那么最后一个位置只能放最后一种，而哪前m-1种呢，C(m, m-1)

故dp： f(m,n)=mf(m,n-1)+mf(m-1,n-1)

n个不同的数划分为m个无标签的非空集合(第二类Striling数)
n-1个数划分了m-1个非空集合，则最后一个数必须单独成集合，f(n-1, m-1)
n-1个数划分了m个集合，最后一个数随机丢进一个，f(n-1, m)*m,
n个数划分了m-1个集合，不成立

f(n, m)=f(n-1, m-1) + m*f(n-1,m)

n个不同的数划分为m个有标签的非空集合
n-1个数划分了m-1个非空集合，则最后一个数必须单独成集合，但m-1个集合有标签，C(m, m-1)f(n-1, m-1)
n-1个数划分了m个集合，最后一个数随机丢进一个，f(n-1, m)m,
n个数划分了m-1个集合，不成立

f(n, m)=mf(n-1, m-1) + mf(n-1,m)

Posted by richard爱闹 - 3月 22 2015
如需转载，请注明： 本文来自 Richard

codejam一道题目 2009 Round1C ProA

https://code.google.com/codejam/contest/189252/dashboard#s=p0

主要bug是没有单独处理可能只有进制为1的情况，例如aaaaa这样只有一种字符，另外自己调试了很长时间，

看了大神代码之后发现自己对于字符的习惯用int数组，其实用map更简洁，处理情况要少很多，因为访问的其他地方还要单独判断。

另外就是最好化繁为简，先把进制转化好，然后一个循环就可以算出数了，之前的话边处理变算，情况多容易出错。
而且还不需要专门index映射一下，给自己找麻烦，编程复杂度降低比较好。另外就是判断进制为0不是用dig，最好用map大小，这样可以处理
进制为1时候的特殊情况

int main()
{

#ifndef ONLINE_JUDGE
    freopen ("A-small-practice.in" , "r" , stdin);
    freopen ("A-small-practice.out" , "w" , stdout);
#endif

    int t;string str;
    cin>>t;
    unordered_map<char, int> mp;
    for(int ti=1;ti<=t;ti++)
    {
        mp.clear();
        cin>>str;int n=str.size();
        vector<int> num;
        int dig=0;
        for(int i=0;i<n;i++)
        {
            if(!i) num.push_back(1), mp[str[i]]=1;
            else if(mp.find(str[i])==mp.end())
            {
                num.push_back(dig);
                mp[str[i]]=dig++;
                if(dig==1) dig=2;
            }
            else
            {
                num.push_back(mp[str[i]]);
            }
        }
        if(mp.size()==1) dig=2;
        //for(auto e: num) cout<<e<<" ";
        reverse(num.begin(), num.end());LL wei=1, sum=0;
        for(int i=0;i<num.size();i++)
        {
            sum+=num[i]*wei;wei*=dig;
            //cout<<sum<<endl;
        }
        printf("Case #%d: %I64d\n", ti, sum);
    }
    return 0;
}

Posted by richard爱闹 - 3月 20 2015
如需转载，请注明： 本文来自 Richard

今天打算重写01背包，想当年算法课上那个版本现在看来真是最原始的，空间未优化，现在这个不仅空间优化，而且还是一维的推进，
比滚动数组还要简洁，感谢编程菜菜，好像fawkes大神也是这么写的。因为从后面开始递推的话，同行前列的状态还是上一行的状态，
刚好直接利用。另外01背包有点局限了，之前有一个数组里找k个长为m的不想交连续子序列和的最大值其实也是01背包的dp，不能过于局限为装东西。

int n, wei;
while(cin>>n>>wei)
{
    for(int i=0;i<n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++) for(int j=wei;j>=w[i-1];j--)
            dp[j]=max(dp[j], dp[j-w[i-1]]+v[i-1]);
    cout<<dp[wei]<<endl;
}

Posted by richard爱闹 - 3月 20 2015
如需转载，请注明： 本文来自 Richard

最近犯的编程错误

1. 一道扫描二维矩阵one row(4个方向最长的同色有多长)，以下是错误代码 GCJ2010(Round1A ProA)

   for(int i=0;i<n;i++) for(int j=0;j<n;j++)
   {

    int ii=i, jj=j;
    char cur=str[i][j];
    if(cur=='.') continue;
    int rowc=1, colc=1, first=1, second=1;
    for(int k=0;k<8;k++)
    {
        int cnt=0;
        while(inrange(ii+dx[k], jj+dy[k]) && str[ii+dx[k]][jj+dy[k]]==cur) ii+=dx[k], jj+=dy[k], cnt++;
        if(k<2) rowc+=cnt;
        else if(k<4) colc+=cnt;
        else if(k<6) first+=cnt;
        else second+=cnt;
    }
    if(rowc>=K || colc>=K ||first>=K || second>=K)
    {
        //cout<<i<<" "<<j<<" "<<rowc<<" "<<colc<<" "<<first<<" "<<second<<endl;
        if(cur=='R') r=1;
        else if(cur=='B') b=1;
    }
   

   }

一直出错，找不到问题，最后还是debug才发现ii=i, jj=j, 这两句应该放到for(k=0->8)循环里面，因为每个方向初始化都要一次
2.CF296Div2ProB
这题是一个编程题，关键是设计数据结构，我没想清楚，然后一开始以为要hash存每个si ti的位置的map，然后又改成vector map[26], 类似这种
后来想清楚，其实对于一种字符map只要存任意一个位置就可以，答案是一样的，因此可以onepass扫描，但是交的代码只看了ump[si], 而忽略了mp[ti]
的情况，例如这种
c b
e c
也就说对于swap减一的情况没有想清楚还要判ump[ti], 只是粗略举例子说swap-2的时候mp[si]就可以了

3.第一道题目反应了很久，本来是一直减，后来发现超时
然后改成递归发现爆栈，后来改循环，发现其实就是辗转相除的运用。结果最后发现有一个分支没有return

LL f(LL a, LL b)
{
    if(a<b) return f(b, a);
    LL ans=0;
    while(a>1 && b>1 && a!=b)
    {
        ans+=(a/b);
        a%=b;
        if(a<b) swap(a, b);
    }
    if(a==b) return ans+1;
    else if(a==1) return ans+b;
    else if(b==1) return ans+a;
    return ans;
}

b

Posted by richard爱闹 - 3月 18 2015
如需转载，请注明： 本文来自 Richard

这里面遇到了一个小问题，一直每调出来，getline(istr, cur, ‘/‘)这里面其实是如果一开始有一个/会多出一个空格来，因此要特殊处理这个，
另外/不需要转移，\需要转移为\, 记忆方法是\n \t这种里面\是用来转义的，因此Windows目录的\需要转义，Unix则不需要

https://code.google.com/codejam/contest/635101/dashboard#s=p0

多叉树，非常像Trie。出现的问题包括Node root 竟然不能作为参数传递，原因不明，于是改为Node*，然后里面发现不同目录可以重名，于是不能全局hash，然后发现又不是trie的26叉树
如果只有小写字母的话，过一会儿才想到每个Node定义一个hash表。

代码最大的问题就是之前的istringstream来split字符串忘记处理第一个空格了。

/*
Author: richard
Contact: zhangruichang112@gmail.com
*/
#include<set>
#include<map>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cstdio>
#include<string>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<fstream>
#include<iostream>
#include<algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long LL;
typedef unsigned long long ULL;
//int, -2^31~2^31-1    -2.1*10^9~2.1*10^9 (-2147483648-2147483647)
//unsigned int, 0~2^32-1  0~4.2*10^9
//long long  -2^63~2^63-1 -9*10^18~9*10^18
//unsigned long long 0~2^64-1  0~1.8*10^19
typedef pair<int, int> pii;
#define f first
#define s second
int getint(){
    int t = 0, flag = 1; char c = getchar();
    while (c<'0' || c>'9' || c == '-')
    {
        if (c == '-')
            flag = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
        t = t * 10 + c - '0', c = getchar();
    return t*flag;
}
int GCD(int m, int n)
{
    if(!m) return n;
    return GCD(n%m, m);//yushu and chushu
}
//int a[maxn], n;
int n, m;
string str[100], query[100];
struct Node
{
    string val;
    unordered_map<string, Node*> next;
    Node():val("")
    {
        next.clear();
    }
};
Node* root;
void BuildTree()
{
    for(int i=0;i<n;i++)
    {
        Node* p=root;
        istringstream istr(str[i]);
        string cur;
        while(getline(istr, cur, '/'))
        {
            if(cur=="") continue;
            if(p->next.find(cur)==p->next.end())
            {
                Node* tmp=new Node();
                p->next[cur]=tmp;;
                p=tmp;
            }
            else
                p=p->next[cur];
        }
    }
}

int QueryTree()
{
    int ans=0;
    for(int i=0;i<m;i++)
    {
        Node*p=root;
        istringstream istr(query[i]);
        string cur;
        while(getline(istr, cur, '/'))
        {
            if(cur=="") continue;
            if(p->next.find(cur)==p->next.end())
            {
                Node* tmp=new Node();
                p->next[cur]=tmp;;
                p=tmp;ans++;
            }
            else
                p=p->next[cur];
        }
    }
    return ans;
}

int main()
{

#ifndef ONLINE_JUDGE
    freopen ("A-large-practice.in" , "r" , stdin);
    freopen ("A-large-practice.out" , "w" , stdout);
#endif

    int t;
    cin>>t;
    for(int ti=1;ti<=t;ti++)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>str[i];
        for(int i=0;i<m;i++) cin>>query[i];
        root=new Node();
        BuildTree();
        int ans=QueryTree();
        printf("Case #%d: %d\n", ti, ans);
    }
    return 0;
}

Posted by richard爱闹 - 3月 17 2015
如需转载，请注明： 本文来自 Richard

为什么用B+树而不用B树作为数据库索引文件系统？
1) B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2) B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
读者点评
本文评论下第149楼，fanyy1991针对上文所说的两点，道：个人觉得这两个原因都不是主要原因。数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

总结一下就是，内部节点只是索引节点，没有具体信息，更小，因此可以放更多关键字的索引，读写磁盘次数少，查询更快。另外每个query都是走到叶子，查询比较稳定平均，
但是个人感觉这个站不住脚，然后另外是说数据库里基于范围的查询非常频繁，B+只是关键字的直接查询，因此更好，而B树是每个都从root到leaf不太好。

这题一开始没思路，可能还是见得题目少，后来一问朱泽伟说是推公式，这个也比较好想，数据10^18这么大，极有可能是推公式，不太可能是dp，因此枚举了一下
最高点的位置，就找到了规律，再用一下二项式定理，2^n=C(n,0)+…C(n,n) 就可以得知

答案是2^n-2,但是n=1时候发现不对，于是特判n=1输出1，但是问题来了，2^(10^18)咋算，如果直接循环算，超时，二分算sumsum是LLLL溢出，然后朱泽伟说找循环节，
但是也没有过。

最终问了cxlove大神给了一段LL*LL % LL的代码

LL MultMod(LL a,LL b,LL MOD){
    a %= MOD;
    b %= MOD;
    LL ret = 0;
    while(b){
        if (b & 1){
            ret += a;
            if(ret >= MOD) ret -= MOD;
        }
        a = a << 1;
        if (a >= MOD) a -= MOD;
        b = b >> 1;
    }
    return ret;
}

其实就是模拟一下每一位数乘，然后取模，再累加取模就可以了。

最后还是一直WA，后来发现F(n)可能出现<0因为是MOD的指数幂，和之前的思维不太一样，因此需要((F(n)-2LL)%MOD+MOD)%MOD， 另外cxlove说-1%2=-1, 也即负数摸上正数必小于0
这点值得怀疑，之前好像出现过等于正数的情况，fawkes大神说这个与编译器有关，再次感谢cxlove大神，CF2200+rating了，solved problems 1300+

附上代码

LL MultMod(LL a,LL b,LL MOD){
    a %= MOD;
    b %= MOD;
    LL ret = 0;
    while(b){
        if (b & 1){
            ret += a;
            if(ret >= MOD) ret -= MOD;
        }
        a = a << 1;
        if (a >= MOD) a -= MOD;
        b = b >> 1;
    }
    return ret;
}
LL MOD;
LL F(LL n)
{
    if(!n) return 1LL;
    LL sum=F(n/2LL);
    if(n&1) return MultMod(2LL, MultMod(sum, sum, MOD), MOD);
    else return MultMod(sum, sum, MOD);
}
int main()
{
    LL n;
    while(cin>>n>>MOD)
    {
        if(n==1) cout<<1%MOD<<endl;
        else cout<<((F(n)-2LL)%MOD+MOD)%MOD<<endl;
    }
    return 0;
}

Posted by richard爱闹 - 3月 15 2015
如需转载，请注明： 本文来自 Richard

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&cid=571
这道题目看起来很简单，其实写残了，好多bug没处理，包括第一遍扫到题目的leading zero到后面就忘得一干二净。

高精度加法主要还是需要先reverse之后然后再加，加完之后要去掉后导0，然后再reverse结果，里面有一个地方改成char*之后，要存储len然后循环每次不必调用strlen()
这是一个之前的错误，string就不会出现这个问题。

WA和T了无数发后，终于A了

T有char开的小了，导致\0没有地方放，还有没处理后导0，以及处理前导0忘记把全是0的单独处理了，等等。再次感谢cxlove帮我看代码

最后修改后的相对clean的代码

char DigToCh(int num)
{
    if(num<=9) return char(num+'0');
    else return char(num-10+'a');
}

int ChToDig(char c)
{
    if(c<='9' && c>='0') return (c-'0');
    else return c-'a'+10;
}
char str[100][201];
int Len[100];
void RemoveBehindZero(char* str, int &n)
{
    int i;
    for(i=n-1;i>=0;i--) if(str[i]!='0') break;
    if(i<0)
    {
        str[0]='0', str[1]='\0', n=1;
        return ;
    }
    str[i+1]='\0';
    n=i+1;
}
int main()
{
    int n, b;
    while(cin>>n>>b)
    {
        for(int i=0;i<n;i++) scanf("%s", str[i]), getchar();
        //for(int i=0;i<n;i++) cout<<str[i]<<endl;
        int maxlen=0;
        for(int i=0;i<n;i++)
        {
            int len=strlen(str[i]);
            //RemoveLeadZero(str[i], len);
            reverse(str[i], str[i]+len);
            Len[i]=len;
            maxlen=max(maxlen,len);
        }
        char ans[maxn];int ansi=0;
        for(int i=0;i<maxlen;i++)
        {
            int sum=0;
            for(int j=0;j<n;j++)
            {
                if(i<Len[j]) sum+=ChToDig(str[j][i]);
            }
            sum%=b;
            ans[ansi++]=DigToCh(sum);
            //ans.push_back();
        }
        ans[ansi]='\0';
        int len=ansi;
        RemoveBehindZero(ans, len);
        reverse(ans, ans+len);
        cout<<ans<<endl;
    }
    return 0;
}

Posted by richard爱闹 - 3月 15 2015
如需转载，请注明： 本文来自 Richard

这种题我非常不擅长，对于给定的m，s找到最大和最小的数，使得位数分别为m且各位数之和为s，如果不存在返回-1

这道题目其实如果没写好可能会写残掉，就比如我。夫神思路非常清楚，而且1A，关键是他能够代码重用。

http://codeforces.com/contest/489/problem/C
我已开始自己写就是贪心的去试，最大的就高位大，最小的从低位开始选大的，同时保证第一位至少为1。

最大的代码倒还好，

string MaxAns(int m, int s)
{
    string maxans(m, '0');
    int remain=s;
    for(int i=0;i<m;i++)
    {
        maxans[i]=min(remain, 9)+'0';
        remain-=(maxans[i]-'0');
    }
    if(remain) return "-1";
    return maxans;
}

最小的话我一直出错，已经各种corner case，例如s=0,等等。后来夫神说min和max很相像，因此可以重用这段，但是reverse之后可能高位为0，
因此再s-1去调用，高位再改为1，就可以了。

最主要是我即使按照这个思路还是一直wa，后来总结s=0的情况最好是单独拿出来处理，里面可能因为s=0就出错，于是clean的代码终于被我搞好了T T

string MaxAns(int m, int s)
{
    string maxans(m, '0');
    int remain=s;
    for(int i=0;i<m;i++)
    {
        maxans[i]=min(remain, 9)+'0';
        remain-=(maxans[i]-'0');
    }
    if(remain) return "-1";
    return maxans;
}
string MinAns(int m, int s)
{
    string minans=MaxAns(m, s);
    if(minans=="-1") return "-1";
    reverse(minans.begin(), minans.end());
    if(minans[0]!='0') return minans;
    minans=MaxAns(m, s-1);
    if(minans=="-1") return "-1";
    reverse(minans.begin(), minans.end());
    minans[0]='1';
    return minans;
}

int main()
{
/*
#ifndef ONLINE_JUDGE
    freopen ("in.txt" , "r" , stdin);
    freopen ("out.txt" , "w" , stdout);
#endif
*/
    int m ,s;

    while(cin>>m>>s)
    {
        if(!s && m>=2) cout<<"-1 -1"<<endl;
        else if(!s && m==1) cout<<"0 0"<<endl;
        else
            cout<<MinAns(m, s)<<" "<<MaxAns(m, s)<<endl;
    }
    return 0;
}

Posted by richard爱闹 - 3月 15 2015
如需转载，请注明： 本文来自 Richard