re: NWERC 2009 王之昊 2010-11-04 17:12
re: fzu 1775 Counting Binary Trees 王之昊 2010-09-10 13:16
@lisongs1
比如算C(10,3) % 4 等價于 [ (10*9*8) / (3*2*1) ] % 4.
然后又等價于 { [ 2^4 * (5*9*1) ] / [ 2^1 * (3*1*1) ] } % 4,相當于把和4不互素的因子提出來,這種因子是很少的。
然后得到 [ (5*9*1) / (3*1*1) ] % 4 直接用模或者求逆算就可以了
比如算C(10,3) % 4 等價于 [ (10*9*8) / (3*2*1) ] % 4.
然后又等價于 { [ 2^4 * (5*9*1) ] / [ 2^1 * (3*1*1) ] } % 4,相當于把和4不互素的因子提出來,這種因子是很少的。
然后得到 [ (5*9*1) / (3*1*1) ] % 4 直接用模或者求逆算就可以了