MTF0000 題解

MTF0000

# MTF0000 題解

## **unique1**

### 創作靈感

在找工作時，接觸了一些公司為了徵才而準備的資料結構與演算法的面試題，發現面試題相對於一般的演算法競賽，更注重記憶體的使用量，除了優化時間複雜度外，也會希望面試者能優化記憶體使用量。所以覺得偶爾出一些在記憶體用量上找碴的題目對大家可能也有所幫助～

同時，以測試一個新 Judge 平台的角度而言，我們也想準備一道能好好測試記憶體限制能否正常發揮的題目，於是此題就誕生啦！

### 解法

要從中選出盡量多兩兩相異的數，就等同問讀入中相異數的個數。並且在 c++ 裡，對於排序好的數列， **STL** 中有一個函數 [unique](http://www.cplusplus.com/reference/algorithm/unique/) 可以直接做到這件事，於是若不考慮記憶體的使用量的話，下列程式碼即可算出正確的答案：　
```cpp
#include<bits/stdc++.h>
int a[2000000],n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    printf("%d\n",std::unique(a,a+n)-a);
}
```
但若上傳這段程式碼，你將會獲得 MLE(Memory Limit Exceeded)，這是因為一個 **int** 所需的記憶體量為 $4$ bytes，所以 $2 \times 10^6$ 個 **int** 所需的記憶體量 $= 4 \times 2 \times 10^6$ bytes $\approx 8000$ **KB** ，超過了本題 $4096$ **KB** 的記憶體限制。

我們的預期解答如下：
由於我們有 $A_i \le A_{i+1}$ 的限制，所以相同的數一定都是在讀入中的連續的區塊，於是我們若算出區塊數量，就能算出相異的個數。當讀入的數一個一個進來時，若當前讀入地數和上一個讀入地數相異，就代表我們從一個區塊離開並進入下一個區塊，令在讀入的過程中發生這樣的事的次數為 $t$，本題的答案就會是 $t+1$。

使用這個方法，我們就只需要紀錄當前讀入的數和上一個讀入的數即可。

### 賽後短評

賽前完全沒料到會有那麼多人在賽中獲得 **MLE** 的...，我還特別在題目裡強調說 **請注意本題記憶體限制只有 4 MB** 耶！該不會這是許多人第一次碰到限制記憶體用量的題目吧 >__<

## **operator1**

### 創作靈感

有一個還算經典的題目是這樣的：

> 給你兩個正整數 $a, b$ ($a \le b$)，請計算 $a$ xor $(a+1)$ xor $\ldots$ xor $b$ 的值

市面上有很多此問題的變形題，所以我也來基於這個問題變形一下，把二進位改成三進位！

### 解法

看到這類題目，相信競賽經驗豐富，但剛好就是沒看過這種題目類型的人，會使用一種方法來觀察答案：令 $f(n) = 1$ @ $2$ @ $\ldots$ @ $n$，先把 $f(0)$、$f(1)$、$f(2)$、$\ldots$ 的值都印出來觀察看看。(因為讀入為 $a, b$ 時，答案將是 $f(b)-f(a-1)$ (這裡的減號是三進位的不退位減法)，只要會算 $f(n)$ 的值，就可以解出這題)

印出來結果如右：``0,1,0,3,7,0,6,4,0,9,19,0,12,25,0,15,22,0,18,10,0,``


於是就很開心地發現，$3$ 的倍數的位置都是 $0$！

就算不會證明，相信得到這個結論的人就可以解出這題了。

於是要求 $f(n)$ 時，就只要對最後 $n\%3$ 做 @運算即可！

但要證明應該也不難吧我想 >__<
把除以 $3$ 值相同的三個數做@運算，個位數字分別是 $0, 1, 2$，相加就是 $0$，其他位數都一樣，三個數相加也會是 $0$。證明完畢！

### 賽後短評

賽前好猶豫這題和第三題哪個比較難...，最終從 scoreboard 看來是猜對了！

## **factor1**

### 創作靈感

這題其實是在準備今年2017年 [IOIcamp](https://www.facebook.com/ioicamp/) 的數論的題目，在腦中搜尋數論經典題時想到的，算是個還蠻常見的複雜度為 $O(\sqrt{n})$ 的數論題，我相信在其他 Judge可能也找的到一樣的題目，那時因為覺得這題太簡單了所以就放生它，換了另外一題放在 **IOIcamp**。現在覺得是時候了(因為準備這題的所需時間超短XD)，就把當時的靈感從暫存器裡提取出來。

### 解法

以下是個會超時但能算出正確答案的程式碼：
```cpp
int count_factor(long long x){
    long long i,ret=0;
    for(i=1;i*i<=x;i++){
        if(x%i==0)ret+=2;
    }
    if((i-1)*(i-1)==x)ret--;
    return ret;
}
// solve(a,b)將回傳本問題答案
long long solve(long long a,long long b){
    long long ret=0;
    for(long long i=a;i<=b;i++){
        ret+=count_factor(i);
    }
    return ret;
}
```
從這份程式碼幾乎是看不到能優化到在時限內能解出的可能。於是我們先用更數學的觀點來看此問題。

令 $fac(n)$ 為 $n$ 的因數個數，$f(n) = \sum\limits_{i=1}^{n}fac(i)$，題目所求即是 $f(b)-f(a-1)$，所以我們現在要找個方法來快速算 $f(x)$。現在把 $f(n)$ 改寫成
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}$ $[j$ 是 $i$ 的因數$]$ (如果敘述為真，[敘述] $= 1$，否則為 $0$)。

在組合計數或微積分的問題裡面有個很常見的技巧就是交換 $\sum$ 的前後順序！(Interchanging the Order of Summation)，於是我們可以得到等式：
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}$ $[j$ 是 $i$ 的因數$]$ = $\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{n}$ $[j$ 是 $i$ 的因數$]$
以二維的加總($\sum$)來說，可以想像成：對於所有 $i,j$，把 [j$ 是 $i$ 的因數$] 的值填入二維表格中的座標為 $(i,j)$ 的那格，原本的式子是先計算相同 $y$ 座標的數的總和後在全部加起來，後來的式子則是先計算相同 $x$ 座標的數的總和。

但改寫成 $\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{n}$ $[j$ 是 $i$ 的因數$]$ 有什麼用呢？請認真思考一下式子裡層的：$\sum\limits_{i=1}^{n}$ $[j$ 是 $i$ 的因數$]$ 意思
啊這不就是 $\lfloor n/j\rfloor$ ($\lfloor x\rfloor$ 代表 不超過 $x$ 的最大整數)

所以我們推導出 $f(n) = \sum\limits_{j=1}^{n}\lfloor n/j\rfloor$

於是我們能寫出基於這個式子的樸素解如下：
```cpp
int f(long long n){
    long long ret=0;
    for(int i=1;i<=n;i++)
        ret+=n/i;
    return ret;
}
// solve(a,b)將回傳本問題答案
long long solve(long long a,long long b){
    return f(b)-f(a-1);
}
```
現在這份程式碼已經跑得比前面那份還快了，可是還不夠呢...

但這次我們可以更容易地從程式碼看出要怎麼加速了！現在我們關注在這以下兩行程式碼：

```cpp
for(int i=1;i<=n;i++)
    ret+=n/i;
```
對於 $i$ 在 $1 \sim n$ 的範圍內 ``n/i`` 只有 約 $2 \times \sqrt{n}$ 種可能值！ (對於 $\le \sqrt{n}$的 $i$，$n/i$ 的結果都相異，對於 $> \sqrt{n}$ 的 $i$，結果都落在 $1 \sim \sqrt{n}$ 之間) 而且產生相同的值的 $i$ 都是連續的，於是我們就能把程式碼改進，變成如下：
```cpp
long long f(long long n){
    long long i=1,ret=0;
    while(i<=n){
        long long v=n/i;
        long long nxt_i=x/v; //nxt_i = 最大的 x 滿足 n/x 和 n/i 一樣
        ret+=(nxt_i+1-i)*v;
        i=nxt_i+1;
    }
    return ret;
}
```
於是我們就使用了 $O(\sqrt{n})$ 的方法解出這題了！
### 賽後短評

賽後得知，有人因為看了第四題的題目敘述，而去猜想它是在暗示：雖然第四題無法利用 **OEIS** 得到答案，但這題可以。就去搜尋 [OEIS](https://oeis.org/A006218)，就找到了公式：
$a(n) = 2\times(\sum\limits_{i=1}^{floor(\sqrt{n})} floor(n/i)) - floor(\sqrt{n})^2$

能在 **OEIS** 找到公式這件事並不是我所預期的啊啊啊！！！((╯‵□′)╯︵┴─┴) (這式子的證明並不難，大家自己證證看～我題解裡所採用的方法是在類似題裡更容易去思考的方法)

這樣大家知道為什麼會在第四題敘述裡寫：「**OEIS** 是一個令眾多出題者感到頭痛的網站」了吧！它會讓一些原本很困難的題目變得很簡單，使得出題者在出題時，都必須思考 OEIS 提供的資訊會不會讓該題難度下降，使得很多漂亮的題目都不能在參賽者能接觸到網路的比賽上出了。

## **oeis1**

### 創作靈感

這題是為了教大家本地建表的概念而設計的。而且我是想要設計出，並不把數列的每一項都記錄下來，而是記錄其中的幾項，紀錄部分結果，而其它項能從部分結果快速推導的題目。要讓大家知道，就算題目所求的項數很大時，也是有機會可以用本地建表獲得 AC。

另外，本題也可以測試程式碼長度限制的功能，相信賽中有部分人有遇到紀錄太多數而無法上傳的麻煩 XD

### 解法

首先，先把數列 $D$ 的公式改寫成 $D_i = D_{i-1} + f(D_{i-1}) + g(D_{i-1}) + 10$，於是我們就得到了一個只和自己的上一項有關的關係式，這樣我們就可以選定一個數 $x$，在程式碼裡寫死 $D_x, D_{2x}, D_{3x}, \ldots$　的值，如此一來，若從 $D_{i-1}$ 推倒 $D_i$ 的所需時間都不超過 $t$，那對於任何測試資料，就一定能在 $x \times t$ 的時間內求出答案。

由於出題者不想直接貼本題的程式碼，於是改用[費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)求第 $N$ ($N < 10^9$) 項的問題，使用本地建表來解題的程式碼來做示範：
```cpp
// 令 X = 10^7，此程式碼將印出一個包含所有形如 F_{tX} 和 F_{tX+1} 的項數
#include<cstdio>
const int MOD = 1000000007;
int main(){
    int last0=0,last1=1;
    printf("int F[200]={0,1");
    for(int i=2;i<1000000000;i++){
        int now=(last0+last1)%MOD;
        if(i%10000000==1)printf(",%d,%d",last1,now);
        last0=last1;
        last1=now;
    }
    puts("};");
}

```

```cpp
#include<bits/stdc++.h>
const int MOD = 1000000007;
int F[200]={0,1,490189494,640540120,877218207,803548776,792336636,808851781,865390300,196976169,364822946,345273904,34721793,400398684,211176624,324203083,489276259,974106729,560674156,865342814,908460138,945351196,663959822,537402860,351309356,927393756,34728542,846909185,946297609,502819837,646371660,357890353,845895238,786188346,490220918,754032189,981951309,505535123,384152217,5878240,371975563,80688602,71343585,176887776,396013987,58939966,341094152,175761349,47125963,396580227,431043837,209556590,370146386,237581351,872482683,403215026,829535814,241674835,303189210,801393168,967988087,800447448,584343994,49657722,132225666,721876347,306710464,552449914,848719223,830726857,417590676,503416162,103684887,294879735,636741114,458492591,31497600,498260343,550090373,160506850,392460984,947746097,688807392,267466228,903333739,164224057,34803879,775227299,729987547,369610353,541353446,992016211,29563180,300238008,779310126,470469544,573486682,719571781,793777511,221450476,864787550,220121405,969567541,770923794,566334113,57673489,10891922,649415011,689319466,860400491,869935040,772961815,251655405,355165112,732223594,643614158,192043699,638417417,571286786,12479963,4660654,539612979,521818629,512688015,872935933,270634790,905978774,945667489,540377917,337084384,418078,114864556,478613700,410797201,588684121,364467476,878336833,557802238,639284028,679697704,393241336,850278613,770716118,156375227,859137012,221940703,809790292,778343289,801111326,950271398,4258201,827413683,940822230,467449387,125212249,986349289,385921075,65668574,642109873,129710253,530142919,975243705,117421826,850365172,381604439,572433034,207547749,275814297,506593171,12389717,918528888,176452201,861085340,892961352,236563805,712352343,42290336,133406429,916937613,702084335,662356693,442753488,460962947,265150282,816832494,422402570,553560792,95946971,859755617,517042806,993450205,592855736,386573344,516187473,286263480,146233878,278360791,536120382,823805809,751462579};
int main(){
    int n;
    scanf("%d",&n);
    int t=n/10000000;
    int now=F[t*2];    // F[t*10000000] 的值
    int nxt1=F[t*2+1]; // F[t*10000000+1] 的值
    t*=10000000;
    while(t<n){
        int nxt2=(now+nxt1)%MOD;
        now=nxt1;
        nxt1=nxt2;
        t++;
    }
    printf("%d\n",now);
}
```

### 額外補充

有人嫌棄這題本地建表要執行很久...我個人是覺得還好啦，我用我廢廢的筆電建表，也只要 97 秒就跑完了，在等的時間剛剛好去寫正是上傳要用的程式碼 XD 而且這樣的執行時間若是在 Google Code Jam 或是 Facebook Hacker Cup 根本就可以不用建表就使用了！但如果你建表一次需要超過 6 分鐘...或許可以嘗試一些簡單的優化，例如說，在算 $f(x)$ 和 $g(x)$ 的值時，可以預算每 $x \le 10^7$ 的 $f(x)$、$g(x)$ 值，這樣就可以用 $f(x) = f(x/10000000) + f(x\%10000000)$ 等的公式去更快的算出 $f(x)$ 和 $g(x)$，執行時間約只剩下原本的執行時間的 $1/7 \sim 1/6$。

### 賽後短評

本地建表看似簡單，可是在正式比賽使用時也是很吃經驗以及臨場反應，畢竟如果建表要跑 $10$ 分鐘以上，建表的程式如有 Bug，可能要過很久才發現，所以建表時最好要邊建表編印出一些資訊，例如每跑完 $10^7$ 個數就印出中途結果，可能可以掌握一些資訊，例如說一不小心就溢位之類的 XD 這題也為了讓大家以後建表時能更小心謹慎，特地出成答案用使用 unsigned long long 才能儲存答案的範圍 XD 好像也有不少人踩到這個雷。