題目

這題目很哏，真得很哏 哏到我都快不想寫了（結果還是用兩節課 AC 了） 題目略過，要看原題的在這

解法

我看完題目第一個想法就是 DP

。。。然後我就 TLE 了（廢話

因為是要求前 $N$ 項的 $mex$，所以真的會想到 DP 但是請看範圍：$1e9$，怎麼看都會 TLE 所以只能想一下數學解法了

$k = 1$ 的解法不用講了，直接輸出數字就好了 = =（好哏

接著是 $k = 2$，我們觀察一下 $f ( 2, n )$ 的前 $12$ 項： $0, 1, 0, 1, 2, 0, 3, 1, 4, 2, 5, 0, 6$ 經過觀察，其實只要當 $n$ 為偶數時，直接輸出 $\frac{n}{2}$ 就好了

接著再分兩個case : $n$ 為奇術時

case 餘一：$\frac{n}{4}$ 的整數部分 $\to \lfloor \frac{n}{4} \rfloor$ case 餘三：$f ( 2, \frac{n}{2} ) \to$直接對這個函數做遞迴就好

總結一下，函數大概長這樣

$$f ( k, n ) = \begin{cases} n, & \text{if $k$ is $1$} \newline \begin{cases} \frac{n}{2}, & \text{if $n$ is even} \newline \lfloor \frac{n}{4} \rfloor, & \text{if $n = 4\times k + 1 ( k \in \mathbb{R} )$ } \ newline f ( 2, \frac{n}{2} ), & \text{if $n = 4\times k + 3 ( k \in \mathbb{R} )$ } \end{cases}, & \text{if $k$ is $2$ } \end{cases}$$

因為遞迴不需要超過兩次，所以可以視為常數時間內，$O ( 1 )$ 的解法

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define maxN 10005

inline int count ( int n ){
    switch ( n ){
        case 3:
        case 1: return 1;
        case 5:
        case 2: return 0;
        default:
            switch ( n % 4 ){
                case 2:
                case 0: return n / 2;
                case 1: return n / 4;
                case 3: return count ( n / 2 );
            }
    }
    return 0;
}

int main(){
    int k, m;
    scanf ( "%d%d", &k, &m );
    printf ( "%d\n", ( k == 1 ? m : count ( m ) ) );
}

後記(2019/03/23 00:29)

為了能讓這篇文章的函數好看一些 硬生生讓 hexo 支援 mathjax 了 然後上面那個精美的函式，我把原始碼放這邊

$$
f ( k, n ) =
\begin{cases}
	n,                                                                                                & \text{if $k$ is $1$} \newline
\begin{cases}
\frac{n}{2}, & \text{if $n$ is even} \newline
\lfloor \frac{n}{4} \rfloor, &
\text{if $n = 4\times k + 1 ( k \in \mathbb{R} )$ } \ newline
f ( 2, \frac{n}{2} ), & \text{if $n = 4\times k + 3 ( k \in \mathbb{R} )$ }
\end{cases}, & \text{if $k$ is $2$ }
\end{cases}
$$
```