統(tǒng)計(jì)桌面上的不同數(shù)字

【數(shù)學(xué)】n-1一定滿足要求，不斷循環(huán)后，[2,n]都會(huì)在桌子上，答案為n - 1，記得特判n=1的情況。

猴子碰撞的方法數(shù)

【數(shù)學(xué)】正難則反（考慮全集減去對(duì)立事件），只有全部順時(shí)針和逆時(shí)針這兩種情況才不會(huì)相撞，所以答案是2^n - 2（每個(gè)猴子向左或向右是2^n），要用快速冪計(jì)算。為了避免負(fù)數(shù)需要-2再轉(zhuǎn)換到非負(fù)數(shù)上。（pow(2, n, MOD)的范圍是[0, mod - 1]可能是負(fù)數(shù)）

將珠子放入背包中

【排序 + 貪心】問題相當(dāng)于把 weights 劃分成 k 個(gè)連續(xù)子數(shù)組，分?jǐn)?shù)等于每個(gè)子數(shù)組的兩端的值之和。weights[0] 和 weights[n?1] 一定在分?jǐn)?shù)中，最大分?jǐn)?shù)和最小分?jǐn)?shù)相減，抵消了。上一個(gè)子數(shù)組的末尾和下一個(gè)子數(shù)組的開頭一定同時(shí)在分?jǐn)?shù)中。把所有n-1個(gè)weights[i]+weights[i+1]算出來，排序，那么最大的k-1個(gè)數(shù)和最小的k-1個(gè)數(shù)相減，即為答案。

統(tǒng)計(jì)上升四元組

【預(yù)處理 + 枚舉】枚舉中間的j和k更容易計(jì)算。需要計(jì)算在k右側(cè)的比nums[j]大的元素個(gè)數(shù)，記作great[nums[j]]在j左側(cè)的比nums[]小的元素個(gè)數(shù)，記作less[j] [nums[k]]。對(duì)于固定的j和k，根據(jù)乘法原理，對(duì)答案的貢獻(xiàn)為less[j] [num[s]] [k] · great [k] [nums[j]]。維護(hù)方法：倒序遍歷nums，設(shè)xnums[j-1]，對(duì)于x，小于它的數(shù)的個(gè)數(shù)加一，即less[j] [x]加一。