Hi all.
How can we apply the modular multiplicative inverse when calculating
(n choose k) mod p, where 'p' is a prime number.
If you could suggest some related problems, it would be very helpful.
Thanks in advance.
浜屻?/span>1971騫達紝蹇冪悊瀛﹀Ekman涓?/span>Friesen鐨勭爺絀舵渶鏃╂彁鍑轟漢綾繪湁鍏涓昏鎯呮劅錛屾瘡縐嶆儏鎰熶互鍞竴鐨勮〃鎯呮潵鍙嶆槧浜虹殑涓縐嶇嫭鐗圭殑蹇冪悊媧誨姩銆傝繖鍏鎯呮劅琚О涓哄熀鏈儏鎰燂紝鐢?/span>鎰ゆ掞紙anger錛夈侀珮鍏?/span>(happiness)銆佹偛浼?/span> (sadness)銆佹儕璁?/span>(surprise)銆佸帉鎭?/span>(disgust)鍜屾亹鎯?/span>(fear)緇勬垚
浜鴻劯闈㈤儴琛ㄦ儏榪愬姩鐨勬弿榪版柟娉?/span>---浜鴻劯榪愬姩緙栫爜緋葷粺FACS (Facial Action Coding System)錛屾牴鎹潰閮ㄨ倢鑲夌殑綾誨瀷鍜岃繍鍔ㄧ壒寰佸畾涔変簡鍩烘湰褰㈠彉鍗曞厓AU錛?/span>Action Unit錛夛紝浜鴻劯闈㈤儴鐨勫悇縐嶈〃鎯呮渶緇堣兘鍒嗚В瀵瑰簲鍒板悇涓?/span>AU涓婃潵錛屽垎鏋愯〃鎯呯壒寰佷俊鎭紝灝辨槸鍒嗘瀽闈㈤儴AU鐨勫彉鍖栨儏鍐?/span>
FACS鏈変袱涓富瑕佸急鐐?/span>錛?/span>1.榪愬姩鍗曞厓鏄函綺圭殑灞閮ㄥ寲鐨勭┖闂存ā鏉匡紱2.娌℃湁鏃墮棿鎻忚堪淇℃伅錛屽彧鏄竴涓惎鍙戝紡淇℃伅
涓夈?/span>浜鴻劯琛ㄦ儏璇嗗埆鐨勮繃紼嬪拰鏂規硶
1銆佽〃鎯呭簱鐨勫緩绔嬶細鐩墠錛岀爺絀朵腑姣旇緝甯哥敤鐨勮〃鎯呭簱涓昏鏈?/span>:緹庡浗CMU鏈哄櫒浜虹爺絀舵墍鍜屽績鐞嗗緋誨叡鍚屽緩绔嬬殑Cohn-Kanade AU-Coded Facial Expression Image Database(綆縐?/span>CKACFEID)浜鴻劯琛ㄦ儏鏁版嵁搴?/span>;鏃ユ湰ATR寤虹珛鐨?/span>鏃ユ湰濂蟲ц〃鎯呮暟鎹簱(JAFFE)錛屽畠鏄爺絀朵簹媧蹭漢琛ㄦ儏鐨勯噸瑕佹祴璇曞簱
2銆佽〃鎯呰瘑鍒?/span>:
錛?錛夊浘鍍忚幏鍙?/span>:閫氳繃鎽勫儚澶寸瓑鍥懼儚鎹曟崏宸ュ叿鑾峰彇闈欐佸浘鍍忔垨鍔ㄦ佸浘鍍忓簭鍒?/span>銆?nbsp;
錛?錛夊浘鍍忛澶勭悊:鍥懼儚鐨勫ぇ灝忓拰鐏板害鐨?/span>褰掍竴鍖?/span>錛屽ご閮ㄥЭ鎬佺殑鐭錛屽浘鍍忓垎鍓茬瓑銆?/span>
è鐩殑:鏀瑰杽鍥懼儚璐ㄩ噺錛屾秷闄ゅ櫔澹幫紝緇熶竴鍥懼儚鐏板害鍊煎強灝哄錛屼負鍚庡簭鐗瑰緛鎻愬彇鍜屽垎綾昏瘑鍒墦濂藉熀紜
涓昏宸ヤ綔è浜鴻劯琛ㄦ儏璇嗗埆瀛愬尯鍩熺殑鍒嗗壊浠ュ強琛ㄦ儏鍥懼儚鐨勫綊涓鍖栧鐞?/span>(灝哄害褰掍竴鍜岀伆搴﹀綊涓)
錛?錛夌壒寰佹彁鍙?/span>:灝嗙偣闃佃漿鍖栨垚鏇撮珮綰у埆鍥懼儚琛ㄨ堪鈥?/span>濡傚艦鐘躲佽繍鍔ㄣ侀鑹層佺汗鐞嗐佺┖闂寸粨鏋勭瓑, 鍦ㄥ敖鍙兘淇濊瘉紼沖畾鎬у拰璇嗗埆鐜囩殑鍓嶆彁涓嬶紝瀵瑰簽澶х殑鍥懼儚鏁版嵁榪涜闄嶇淮澶勭悊銆?
è鐗瑰緛鎻愬彇鐨勪富瑕佹柟娉曟湁錛氭彁鍙栧嚑浣曠壒寰併佺粺璁＄壒寰併侀鐜囧煙鐗瑰緛鍜岃繍鍔ㄧ壒寰佺瓑
1錛?/span>閲囩敤鍑犱綍鐗瑰緛榪涜鐗瑰緛鎻愬彇涓昏鏄浜鴻劯琛ㄦ儏鐨勬樉钁楃壒寰?/span>,濡傜溂鐫涖佺湁姣涖佸槾宸寸瓑鐨勪綅緗彉鍖栬繘琛屽畾浣嶃佹祴閲?/span>,紜畾鍏跺ぇ灝忋佽窛紱匯佸艦鐘跺強鐩鎬簰姣斾緥絳夌壒寰?/span>,榪涜琛ㄦ儏璇嗗埆
浼樼偣錛氬噺灝戜簡杈撳叆鏁版嵁閲?/span>
緙虹偣錛氫涪澶變簡涓浜涢噸瑕佺殑璇嗗埆鍜屽垎綾諱俊鎭紝緇撴灉鐨勭簿紜т笉楂?/span>
2錛夊熀浜庢暣浣撶粺璁＄壒寰佺殑鏂規硶涓昏寮鴻皟灝藉彲鑳藉鐨勪繚鐣欏師濮嬩漢鑴歌〃鎯呭浘鍍忎腑鐨勪俊鎭?/span>,騫跺厑璁稿垎綾誨櫒鍙戠幇琛ㄦ儏鍥懼儚涓浉鍏崇壒寰?/span>,閫氳繃瀵規暣騫呬漢鑴歌〃鎯呭浘鍍忚繘琛屽彉鎹?/span>,鑾峰彇鐗瑰緛榪涜璇嗗埆銆?/span>
涓昏鏂規硶錛?/span>PCA鍜?/span>ICA錛堢嫭绔嬩富鍏冨垎鏋愶級
PCAè鐢?/span>涓涓?/span>姝ｄ氦緇存暟絀洪棿鏉ヨ鏄庢暟鎹彉鍖栫殑涓昏鏂瑰悜 浼樼偣錛氬叿鏈夎緝濂界殑鍙噸寤烘?/span> 緙虹偣錛氬彲鍒嗘ц緝宸?/span>
ICAè鍙互鑾峰彇鏁版嵁鐨勭嫭绔嬫垚浠斤紝鍏鋒湁寰堝ソ鐨勫彲鍒嗘?/span>
鍩轟簬鍥懼儚鏁翠綋緇熻鐗瑰緛鐨勬彁鍙栨柟娉曠己鐐癸細澶栨潵鍥犵礌鐨勫共鎵幫紙鍏夌収銆佽搴︺佸鏉傝儗鏅瓑錛?/span>灝嗗鑷磋瘑鍒巼涓嬮檷
3錛夊熀浜庨鐜囧煙鐗瑰緛鎻愬彇: 鏄皢鍥懼儚浠?/span>絀洪棿鍩?/span>杞崲鍒?/span>棰戠巼鍩?/span>鎻愬彇鍏剁壒寰侊紙杈冧綆灞傛鐨勭壒寰侊級
涓昏鏂規硶錛欸abor灝忔嘗鍙樻崲
灝忔嘗鍙樻崲鑳藉閫氳繃瀹氫箟涓嶅悓鐨勬牳棰戠巼銆佸甫瀹藉拰鏂瑰悜瀵瑰浘鍍忚繘琛?/span>澶氬垎杈ㄧ巼鍒嗘瀽錛岃兘鏈夋晥鎻愬彇涓嶅悓鏂瑰悜涓嶅悓緇嗚妭紼嬪害鐨勫浘鍍忕壒寰佸茍鐩稿紼沖畾錛屼絾浣滀負浣庡眰嬈＄殑鐗瑰緛錛屼笉鏄撶洿鎺ョ敤浜庡尮閰嶅拰璇嗗埆錛屽父涓?/span>ANN 鎴?/span>SVM 鍒嗙被鍣?/span>緇撳悎浣跨敤錛屾彁楂樿〃鎯呰瘑鍒殑鍑嗙‘鐜囥?/span>
4錛夊熀浜庤繍鍔ㄧ壒寰佺殑鎻愬彇錛?/span>鎻愬彇鍔ㄦ佸浘鍍忓簭鍒楃殑榪愬姩鐗瑰緛錛堜粖鍚庣爺絀剁殑閲嶇偣錛?/span>
涓昏鏂規硶錛氬厜嫻佹硶
鍏夋祦鏄寚浜害妯″紡寮曡搗鐨勮〃瑙傝繍鍔?/span>錛屾槸鏅墿涓彲瑙佺偣鐨?/span>涓夌淮閫熷害鐭㈤噺鍦ㄦ垚鍍忓鉤闈笂鐨?/span>鎶曞獎錛?/span>瀹冭〃紺烘櫙鐗╄〃闈笂鐨勭偣鍦ㄥ浘鍍忎腑浣嶇疆鐨?/span>鐬椂鍙樺寲錛屽悓鏃跺厜嫻佸満鎼哄甫浜嗘湁鍏寵繍鍔ㄥ拰緇撴瀯鐨勪赴瀵屼俊鎭?/span>
鍏夋祦妯″瀷鏄鐞嗚繍鍔ㄥ浘鍍忕殑鏈夋晥鏂規硶錛屽叾鍩烘湰鎬濇兂鏄皢榪愬姩鍥懼儚鍑芥暟f (x, y,t)浣滀負鍩烘湰鍑芥暟錛屾牴鎹?/span>鍥懼儚寮哄害瀹堟亽鍘熺悊寤虹珛鍏夋祦綰︽潫鏂圭▼錛岄氳繃姹傝В綰︽潫鏂圭▼錛岃綆?/span>榪愬姩鍙傛暟銆?/span>
浼樼偣錛氬弽鏄犱簡琛ㄦ儏鍙樺寲鐨勫疄璐紝鍙楀厜鐓т笉鍧囨у獎鍝嶈緝灝?/span>
緙虹偣錛氳綆楅噺澶?/span>
錛?錛夊垎綾誨垽鍒?/span>:鍖呮嫭璁捐鍜屽垎綾誨喅絳?/span>
鍦ㄨ〃鎯呰瘑鍒殑鍒嗙被鍣ㄨ璁″拰閫夋嫨闃舵錛屼富瑕佹湁浠ヤ笅鏂規硶錛?/span>鐢ㄧ嚎鎬у垎綾誨櫒銆佺緇忕綉緇滃垎綾誨櫒銆佹敮鎸佸悜閲忔満銆侀殣椹皵鍙か妯″瀷絳夊垎綾昏瘑鍒柟娉?/span>
1錛?span style="FONT: 7pt 'Times New Roman'"> 綰挎у垎綾誨櫒錛氬亣璁句笉鍚岀被鍒殑妯″紡絀洪棿綰挎у彲鍒嗭紝寮曡搗鍙垎鐨勪富瑕佸師鍥犳槸涓嶅悓琛ㄦ儏涔嬮棿鐨勫樊寮傘?/span>
2錛?nbsp;紲炵粡緗戠粶鍒嗙被鍣細浜哄伐紲炵粡緗戠粶(Artificial Neural Network,ANN)鏄竴縐嶆ā鎷熶漢鑴戠緇忓厓緇嗚優鐨勭綉緇滅粨鏋勶紝瀹冩槸鐢卞ぇ閲忕畝鍗曠殑鍩烘湰鍏冧歡鈥?/span>紲炵粡鍏冿紝鐩鎬簰榪炴帴鎴愮殑鑷傚簲闈炵嚎鎬у姩鎬佺郴緇?/span>銆傚皢浜鴻劯鐗瑰緛鐨?/span>鍧愭爣浣嶇疆鍜屽叾鐩稿簲鐨?/span>鐏板害鍊?/span>浣滀負紲炵粡緗戠粶鐨勮緭鍏ワ紝ANN鍙互鎻愪緵寰堥毦鎯寵薄鐨勫鏉傜殑綾婚棿鍒嗙晫闈€?/span>
紲炵粡緗戠粶鍒嗙被鍣ㄤ富瑕佹湁:澶氬眰鎰熺煡鍣ㄣ?/span>BP緗戙?/span>RBF緗?/span>
緙虹偣錛氶渶瑕佸ぇ閲忕殑璁粌鏍鋒湰鍜岃緇冩椂闂達紝涓嶈兘婊¤凍瀹炴椂澶勭悊瑕佹眰
3錛?nbsp;鏀寔鍚戦噺鏈?/span>(SVM)鍒嗙被綆楁硶錛?/span>娉涘寲鑳藉姏寰堝己銆?/span>瑙ｅ喅灝忔牱鏈侀潪綰挎у強楂樼淮妯″紡璇嗗埆闂鏂歸潰琛?/span>銆?/span>鏂扮殑鐮旂┒鐑偣
鍩烘湰鎬濇兂錛?/span>瀵逛簬闈炵嚎鎬у彲鍒嗘牱鏈紝棣栧厛閫氳繃闈炵嚎鎬у彉鎹?/span>灝?/span>杈撳叆絀洪棿鍙樻崲鍒頒竴涓?/span>楂樼淮絀洪棿錛岀劧鍚庡湪榪欎釜鏂扮┖闂翠腑姹傚彇鏈浼樼嚎鎬у垎鐣岄潰銆傝繖縐嶉潪綰挎у彉鎹㈤氳繃瀹氫箟閫傚綋鐨?/span>鍐呯Н鍑芥暟瀹炵幇錛屽父鐢ㄧ殑涓夌鍐呯Н鍑芥暟涓?/span>:澶氶」寮忓唴縐嚱鏁般?strong>寰勫悜鍩哄唴縐嚱鏁?/strong>銆?/span>Sigmoid鍐呯Н鍑芥暟
4錛?nbsp;闅愰┈灝斿彲澶ā鍨?/span>(Hidden Markov Models, HMM)錛氱壒鐐癸細緇熻妯″瀷銆佸仴澹殑鏁板緇撴瀯錛岄傜敤浜?/span>鍔ㄦ佽繃紼嬫椂闂村簭鍒楀緩妯?/span>錛屽叿鏈夊己澶х殑妯″紡鍒嗙被鑳藉姏錛岀悊璁轟笂鍙鐞嗕換鎰忛暱搴︾殑鏃跺簭錛屽簲鐢ㄨ寖鍥撮潪甯稿箍娉涖?/span>
浼樼偣錛?/span>榪愮敤HMM鏂規硶鑳藉姣旇緝綺劇‘鐨勬弿緇?/span>琛ㄦ儏鐨勫彉鍖栨湰璐ㄥ拰鍔ㄦ佹ц兘
5錛?nbsp;鍏朵粬鏂規硶錛?/span>
鍩轟簬浜鴻劯鐗╃悊妯″瀷鐨勮瘑鍒柟娉曪紝灝嗕漢鑴稿浘鍍忓緩妯′負鍙彉褰㈢殑3D緗戞牸琛ㄩ潰錛屾妸絀洪棿鍜岀伆搴︽斁鍦ㄤ竴涓?/span>3D絀洪棿涓悓鏃惰冭檻銆?/span>
鍩轟簬妯″瀷鍥懼儚緙栫爜鐨勬柟娉曟槸浣跨敤閬椾紶綆楁硶鏉ョ紪鐮併佽瘑鍒笌鍚堟垚鍚勭涓嶅悓鐨勮〃鎯?/span>
鍥涖佺爺絀跺睍鏈?/span>
錛?/span>1錛夐瞾媯掓ф湁寰呮彁楂橈細
澶栫晫鍥犵礌錛堜富瑕佹槸澶撮儴鍋忚漿鍙?/span>鍏夌嚎鍙樺寲鐨勫共鎵幫級
閲囩敤澶氭憚鍍忓ご鎶鏈佽壊褰╄ˉ鍋挎妧鏈?/span>浜堜互瑙ｅ喅錛屾湁涓瀹氭晥鏋滐紝浣嗗茍涓嶇悊鎯?/span>
錛?/span>2錛夎〃鎯呰瘑鍒綆楅噺鏈夊緟闄嶄綆è紜繚瀹炴椂鎬х殑瑕佹眰
錛?/span>3錛夊姞寮哄淇℃伅鎶鏈殑铻嶅悎
闈㈤儴琛ㄦ儏涓嶆槸鍞竴鐨勬儏鎰熻〃鐜版柟寮忥紝緇煎悎璇煶璇皟銆佽剦鎼忋佷綋娓?/span>絳夊鏂歸潰淇℃伅鏉ユ洿鍑嗙‘鍦版帹嫻嬩漢鐨勫唴蹇冩儏鎰燂紝灝嗘槸琛ㄦ儏璇嗗埆鎶鏈渶瑕佽冭檻鐨勯棶棰?/span>
]]>
Computing n choose k mod p
by joshi13 » Tue Apr 14, 2009 4:49 am
Re: Computing n choose k mod p
by mf » Tue Apr 14, 2009 10:56 am
You could use .
Re: Computing n choose k mod p
by maxdiver » Tue Apr 14, 2009 12:03 pm
There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.
C_n^k = n! / (k! (n-k)!)
Let's learn how to compute n! mod p, but factorial without factors p and so on:
n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
I name this 'strange factorial'.
If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS
If p is not large, then GOTO BEGIN_SCARY_MATHS:
Else - skip the rest of the post
BEGIN_SCARY_MATHS:
After taking each factor mod p, we get:
n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
So 'strange factorial' is really several blocks of construction:
1 * 2 * 3 * ... * (p-1) * i
where i is a 1-indexed index of block taken again without factors p ('strange index' ).
The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.
So... After so much brainfucking maths I must give a code
Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
END_SCARY_MATHS:
So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).
P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...
C_n^k = n! / (k! (n-k)!)
Let's learn how to compute n! mod p, but factorial without factors p and so on:
n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
I name this 'strange factorial'.
If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS
If p is not large, then GOTO BEGIN_SCARY_MATHS:
Else - skip the rest of the post
BEGIN_SCARY_MATHS:
After taking each factor mod p, we get:
n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
So 'strange factorial' is really several blocks of construction:
1 * 2 * 3 * ... * (p-1) * i
where i is a 1-indexed index of block taken again without factors p ('strange index'
).The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.
So... After so much brainfucking maths I must give a code
- Code: Select all
int factmod (int n, int p) {
long long res = 1;
while (n > 1) {
long long cur = 1;
for (int i=2; i<p; ++i)
cur = (cur * i) % p;
res = (res * powmod (cur, n/p, p)) % p;
for (int i=2; i<=n%p; ++i)
res = (res * i) % p;
n /= p;
}
return int (res % p);
}
Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
END_SCARY_MATHS:
So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).
P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...
錛堣漿杞斤細http://acm.uva.es/board/viewtopic.php?f=22&t=42690&sid=25bd8f7f17abec626f2ee065fec3703b錛?
]]>