簽到，略。
簡單貪心，先往右邊走，然後逐步往左邊走。
答案就是出現次數最多的字元出現的次數。
容易發現只有當 K 1 , 1 = 1 K_{1, 1} = 1 K1,1=1 時輸出和原矩陣相同，否則一定會收斂到 O O O。
題意：定義
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,0x+bt,0)f(dt,1,ct,1x+bt,1)f(dt,kt−1,ct,kt−1x+bt,kt−1)f(dt,kt,ct,ktx+bt,kt)x≤at,0at,0<x≤at,1⋮at,kt−2<x≤at,kt−1at,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,iat,i+bt,i)=f(dt,i+1,ct,i+1at,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=∑tkt。
題意：有 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 值為其所有質因子次冪的和，如果該數是奇數就還要加一。
題意：給定 [ 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 篩即可。
原題題意夠簡單了，不敘述。
說起來這還是一個原題，Comet OJ Contest 12 出過。不妨去看那一題的解法。
題意：給定一個初始多項式 f 1 ( x ) = ∑ i = 0 n a i x i f_1(x)= \sum_{i=0}^{n}a_i x^i f1(x)=∑i=0naixi，對於 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)=bifi−1′(x)+cifi−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+cix) 中，
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−1en−i−1f1(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=0nwixi。展開發現
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∑ejk!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)。
待補。。。
待補。。。
待補。。。
待補。。。