1010 Reports

簽到，略，

1003 Express Mail Taking

簡單貪心，先往右邊走，然后逐步往左邊走，

1007 CCPC Training Class

答案就是出現次數最多的字符出現的次數，

1011 3x3 Convolution

容易發現只有當 K 1 , 1 = 1 K_{1, 1} = 1 K1,1?=1 時輸出和原矩陣相同，否則一定會收斂到 O O O，

1006 Robotic Class

題意：定義 n n n 個分段函式，每個函式形如
f ( t , x ) = { f ( d t , 0 , c t , 0 x + b t , 0 ) x ≤ a t , 0 f ( d t , 1 , c t , 1 x + b t , 1 ) a t , 0 < x ≤ a t , 1 ? f ( d t , k t ? 1 , c t , k t ? 1 x + b t , k t ? 1 ) a t , k t ? 2 < x ≤ a t , k t ? 1 f ( d t , k t , c t , k t x + b t , k t ) a t , k t ? 1 < x f(t, x) = \begin{cases} f\left(d_{t, 0}, c_{t, 0}x +b_{t, 0}\right)& x \le a_{t, 0} \\ f\left(d_{t, 1}, c_{t, 1}x +b_{t, 1}\right) & a_{t, 0}<x \le a_{t, 1} \\ & \vdots \\ f\left(d_{t, k_t - 1}, c_{t, k_t - 1}x +b_{t, k_t - 1}\right) & a_{t, k_t - 2}<x \le a_{t, k_t - 1} \\ f\left(d_{t, k_t}, c_{t, k_t}x +b_{t, k_t}\right) & a_{t, k_t - 1}<x \\ \end{cases} f(t,x)=????????????????f(dt,0?,ct,0?x+bt,0?)f(dt,1?,ct,1?x+bt,1?)f(dt,kt??1?,ct,kt??1?x+bt,kt??1?)f(dt,kt??,ct,kt??x+bt,kt??)?x≤at,0?at,0?<x≤at,1??at,kt??2?<x≤at,kt??1?at,kt??1?<x?

t t t 之間形成一個 DAG，只有 n n n 沒有出邊，其中 f ( n , x ) = x f(n, x) = x f(n,x)=x，問 ? 1 ≤ i ≤ n \forall 1 \le i \le n ?1≤i≤n， f ( i , x ) f(i, x) f(i,x) 是否是連續函式，

顯然可以在 O ( n log ? n ) O(n \log n) O(nlogn) 時間內用二分計算出任意的 f ( t , x ) f(t, x) f(t,x)，

假設現在要驗證 f ( t , x ) f(t, x) f(t,x) 的連續性，如果對于任意的 i i i， f ( d t , i , x ) f(d_{t, i}, x) f(dt,i?,x) 都是連續函式，那么只要檢查在分段的邊界上 f ( t , x ) f(t, x) f(t,x) 是否連續即可，即是否有對于任意的 i i i，有 f ( d t , i , c t , i a t , i + b t , i ) = f ( d t , i + 1 , c t , i + 1 a t , i + b t , i + 1 ) f\left(d_{t, i}, c_{t, i}a_{t, i} + b_{t, i}\right)= f\left(d_{t, i+1}, c_{t, i+1}a_{t, i} + b_{t, i+1}\right) f(dt,i?,ct,i?at,i?+bt,i?)=f(dt,i+1?,ct,i+1?at,i?+bt,i+1?)，

時間復雜度 O ( T n K log ? n ) , K = ∑ t k t O(TnK\log n), K = \sum_t k_t O(TnKlogn),K=∑t?kt?，

1005 Lunch

題意：有 n n n 堆石子，每次可以選擇一個數目 l > 1 l>1 l>1 的堆，將其分割為 k > 1 k>1 k>1 個數目為 l k \frac{l}{k} kl? 的堆，所有堆均為 1 1 1 時當前玩家輸，問先手是否必勝，

我好像只會打表找規律…

規律就是每個數的 SG 值為其所有奇質因子次冪的和，如果該數是偶數就還要加一，

1002 Graph Theory Class

題意：給定 [ 2 , n + 1 ] [2, n+1] [2,n+1] 這 n n n 個整數，兩個數 i , j i, j i,j 的邊權為 lcm ? ( i , j ) \operatorname{lcm}(i, j) lcm(i,j)，求最小生成樹，

考慮每個數應該和誰連邊，直覺是每個數和其最大的約數連邊，質數連 2 2 2，那么答案就是 [ 2 , n + 1 ] [2, n+1] [2,n+1] 求和然后再加所有范圍內質數的和，最后減掉多算的 4，于是用 min_25 篩即可，

1012 Xor

原題題意夠簡單了，不敘述，

說起來這還是一個原題，Comet OJ Contest 12 出過，不妨去看那一題的解法，

1013 Residual Polynomial

題意：給定一個初始多項式 f 1 ( x ) = ∑ i = 0 n a i x i f_1(x)= \sum_{i=0}^{n}a_i x^i f1?(x)=∑i=0n?ai?xi，對于 2 ≤ i ≤ n 2\le i\le n 2≤i≤n，有 f i ( x ) = b i f i ? 1 ′ ( x ) + c i f i ? 1 ( x ) f_i(x) = b_i f_{i-1}'(x) + c_if_{i-1}(x) fi?(x)=bi?fi?1′?(x)+ci?fi?1?(x)，求 f n ( x ) f_n(x) fn?(x) 的系數，

設 e i e_i ei? 為 ∏ i = 2 n ( b i + c i ) \prod_{i=2}^{n} (b_i + c_i) ∏i=2n?(bi?+ci?) 中，含有 i i i 個 c c c 的項之和（或者說，設 e i e_i ei? 為 ∏ i = 2 n ( b i + c i x ) \prod_{i=2}^{n} (b_i + c_ix) ∏i=2n?(bi?+ci?x) 中， x i x^i xi 的系數），那么有：
f n ( x ) = ∑ i = 0 n ? 1 e n ? i ? 1 f 1 ( i ) ( x ) f_n(x) = \sum_{i = 0}^{n-1}e_{n - i - 1}f^{(i)}_1(x) fn?(x)=i=0∑n?1?en?i?1?f1(i)?(x)

設 f n ( x ) = ∑ i = 0 n w i x i f_n(x) = \sum_{i=0}^{n}w_i x^i fn?(x)=∑i=0n?wi?xi，展開發現
i ! w i = ∑ j + k = i + n ? 1 e j k ! a k i! w_i = \sum_{ j + k = i + n - 1} e_{j} k!a_k i!wi?=j+k=i+n?1∑?ej?k!ak?

后面這個是一個簡單的卷積，前面 e e e 怎么求？考慮分治，先求 [ l , m i d ] , [ m i d + 1 , r ] [l, mid], [mid + 1, r] [l,mid],[mid+1,r] 兩部分的 e e e，然后用一個卷積合并這兩個部分即可，

時間復雜度為 O ( n log ? 2 n ) O(n\log^2 n) O(nlog2n)，

1004 Chess Class

待補，，，

1001 Art Class

待補，，，

1008 PE Class

待補，，，

1009 Math Class

待補，，，

小結

另，jls 已經在知乎相關回答貼了題解，想看更 official 的題解可以移步那里，