# 111學年度下學期進階班期末考題解

太簡單我就不給`code`了
好累喔

## a896: 五星好平

簡述：
$arr[N]$切成$K$段
每段總和要一樣
切法有幾種？

### #0 遍歷 $O(N)$
直接判每個數字是否相等，是就$1$，反之$0$

### #1 遍歷 $O(N)$
直接$O(N)$跑過去，維護兩個區間的值，查看相等的次數

### #2 greedy $O(N)$
先記一數$sum$為陣列所有值之總和
如果$sum$不整除$K$，則為$0$
不然$O(N)$跑過去維護區間總和，如果到$\frac{sum}{K}$重新記錄維新的區間
如果可以找到$K$個區間並且所有區間的總和都是$\frac{sum}{K}$，就$1$，反之$0$

### #3 math $O(N)$
答案就是$C^N_K-C^{N-1}_K=C^{N-1}_{K-1}$
然後因為有除法，所以要用模逆元

LL a, b, c;
a = b = c = 1;
for(LL i = 1; i < N; i ++ )
    a = (a * i) % mod;
for(LL i = 1; i < K; i ++ )
    b = (b * i) % mod;
for(LL i = 1; i < N - K; i ++ )
    c = (c * i) % mod;
cout << a * inv(b) % mod * inv(c) % mod << endl;

### #4 greedy+math $O(N)$
就跟#2一樣
只是如果在切區間的邊界剛好就是一群的$0$的話就要去記錄起來
因為切的那一刀可以在任意一個$0$之間

舉例來說：
$\{1,\ 0,\ 0,\ 1,\ 0,\ 1\},\ K=3$
要把兩個$0$跟一個$0$記錄起來
然後答案就會是`(2+1)*(1+1)=6`

然後用#2的方法的話要特判只有$0$出現的時候
不然會吃WA

LL sum = 0;
for(auto &i : arr)
    sum += i;
if(sum == 0)
    return /*#3的答案*/
if(sum % K)
    return 0;
sum /= K;
LL cnt = 0, num = 0, ans = 1;
for(LL i = 0; i < N; i ++ ) {
    num += arr[i];
    if(num == sum) {
        LL tmp = 0;
        i ++ ;
        while(i < N && arr[i] == 0)
            tmp ++ ;
        ans *= tmp + 1;
        num = 0;
        cnt ++ ;
    }
}
cout << (cnt == K ? ans : 0) << endl;

### #5 Brute-force $O(C^{N-1}_{K-1})$

直接暴搜每個區間切開的地方
然後區間和一個一個加
最後判是否都相等

#define pb emplace_back
#define ppb pop_back
LL N, K, ans = 0, arr[30];
vector<LL> vec = {0};

void BF(LL p = 1) {
    if(vec.size() == K) {
        vector<LL> tmp;
        for(LL i = 0; i < K; i ++ ) {
            LL num = 0;
            LL r = (i == K - 1 ? N : vec[i + 1]);
            for(LL j = vec[i]; j < r; j ++ )
                num += arr[j];
            tmp.pb(num);
        }
        LL num = tmp[0];
        for(auto &i : tmp)
            if(i != num)
                return;
        ans ++ ;
        return;
    }
    for(LL i = p; i < N; i ++ ) {
        vec.pb(i);
        BF(i + 1);
        vec.ppb();
    }
}

### #6 滾動DP + map $O(KN)$

用`map`陣列去維護`DP`

`mp[k][cur]=總和為`cur時，分成`k`份時的方法數

每當輸入一個$a_i$就更新總和`cur`
並另`j = k ~ 2`去看目前的`cur`是否整除`j`
如果是，就轉移`mp[j][cur] += mp[j - 1][cur / j * (j - 1)]`
因為`j = 1`的時候`cur / j * (j - 1)`就會是`0`，必須單獨拉出來`++`
如果不單獨操作就會爛掉(範測第二個)

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
using namespace std;
using LL = long long;

const LL mod = 1e9 + 7;

int main() {
    IO;
    LL T;
    cin >> T;
    while(T -- ) {
        LL n, k, cur = 0, prev = 0, num;
        cin >> n >> k;
        map<LL, LL> mp[k+1];
        for(LL i = 0; i < n; i ++ ) {
            cin >> num;
            cur += num;
            prev = mp[k][cur];
            /***** 轉移 *****/
            for(LL j = k; j > 1; j -- )
                if(cur % j == 0)
                    mp[j][cur] = (mp[j][cur] + mp[j-1][cur / j * (j - 1)]) % mod;
            /***************/
            mp[1][cur] ++ ;
            mp[1][cur] %= mod;
        }
        cout << (mp[k][cur] - prev + mod) % mod << endl;
    }
}

---

## a901: JoGuessr

函數是一個碗型，可以先用`y=0`對維度`x`三分搜，搜到最小值
再用`x=三分搜最小值`對維度`y`做三分搜
就結束了

最多只要做`16`次左右

好像就沒有什麼好講的了

---

## a919: 最終等級水流消毒劑

${FDCS(n) = \left\{ \begin{array}{l} 1 \qquad \qquad n=1 \\ \Sigma_{k=1}^{n-1}\left[\left(\Sigma_{i=1}^{k}i^{n+k-i}\right)*FDCS(k)\right] \qquad \qquad else \\ \end{array} \right.}$

給定$n$，求$FDCS(n)$

其實這題是拿來送分的:thinking_face:

### #0 手動打表 $O(1)$

就從$1$列到$7$
沒什麼好講的

### #1 遞迴 $O(T*窩不會算反正很大)$

直接套上面的遞迴式
沒什麼好講的

### #2 DP+快速冪 $O(T*N^3)$

直接套上面的遞迴式來做$DP$
因為有大數字次方，所以要用快速冪

LL pwr(LL a, LL b, LL r = 1) {
    for(; b; a = a * a % mod, b >>= 1)
        if(b & 1)
            r = r * a % mod;
    return r;
}

dp[1] = 1;
for(LL n = 2; n < maxN; n ++ ) {
    dp[n] = 0;
    for(LL k = 1; k <= n - 1; k ++ ) {
        LL num = 0;
        for(LL i = 1; i <= k; i ++ ) {
            num = (num + pwr(i, n + k - i)) % mod;
        }
        dp[n] = (dp[n] + num * dp[k]) % mod;
    }
}
for(LL i = 0; i < maxN; i ++ ) {
    if(i % 10 == 0)
        cout << endl;
    cout << dp[i] << ", ";
}

### #3 DP+快速冪 建表 $O(N^3)$

#2+建表
把$T$壓掉

### #4 本地打表 $O(T)$

因為我時限壓$0.1s$，所以一般$DP$不太可能過(除非用毒瘤$IO$優化)
所以要直接在本機先建好表格，直接宣告進陣列，最後直接$O(T)$

這樣的話`dp[]`大概長這樣

LL dp[maxN] = {
0, 1, 1, 10, 1158, 2182470, 305056381, 702082639, 752288299, 477389216,
31433074, 336058181, 593011675, 356559883, 515228734, 815882365, 516395221, 259603426, 275583033, 563699379,
273172876, 803594869, 376459799, 353678446, 586795639, 88101652, 557301679, 207730881, 48371837, 282212452,
7081319, 536987975, 935203404, 266370975, 827004699, 267505718, 174160064, 634356490, 333956301, 511844379,
885388304, 8072856, 136536264, 155852079, 667718194, 811157733, 153136736, 124950019, 574698766, 100319347,
477442139, 634791222, 337075155, 662862920, 726202620, 26903232, 516354729, 881830305, 837006395, 252454848,
254130316, 795729438, 915357505, 761287326, 155107684, 898600656, 619439611, 666466076, 171507634, 611394335,
351657043, 975475572, 716410806, 761030125, 663081781, 162182692, 61447863, 341570784, 675757091, 642697685,
356765037, 227375166, 157736770, 595898735, 608726393, 755658579, 275875603, 78344815, 84461062, 471213261,
972558343, 823928395, 277298156, 488523380, 559463723, 218520738, 980656872, 577939757, 896131049, 147250089,
481006235, 61276048, 824877846, 812981205, 745109522, 174517502, 379894848, 879889549, 685348645, 104539313,
700794798, 12189210, 663846524, 237862331, 865980705, 815936315, 787049217, 266207480, 724294525, 11849353,
756361719, 650254096, 575328055, 383594245, 7484244, 935444700, 282083903, 185725873, 309135729, 799895081,
790130249, 580254395, 254281866, 452919717, 704571890, 928054673, 922186589, 794750560, 585165264, 227130235,
729763789, 802464579, 458137939, 893743199, 81346751, 189344264, 489276569, 45908973, 760498563, 534608392,
526044102, 930290407, 700449761, 505382214, 964680818, 107651495, 62189544, 248248515, 442224332, 401476474,
794880138, 80124355, 644203663, 157393343, 259417538, 46003290, 759758656, 8825068, 31319805, 80114112,
651032734, 831232606, 169192627, 952636179, 539608933, 660187854, 588897357, 311368973, 468315640, 962097104,
753379453, 361652529, 366320888, 452377551, 591283833, 607748576, 335227937, 237841392, 637805222, 154093331,
432773831, 512317024, 419544035, 927480250, 223715398, 616313944, 557918787, 265417324, 296332362, 555793430,
310874129, 94881716, 486139843, 754686377, 489685195, 569580815, 766488173, 811270212, 590056031, 83740899,
201861289, 918415532, 39776803, 755667976, 762858856, 493131157, 293727639, 419363579, 614753101, 490540101,
984408602, 589279324, 895767194, 755172025, 6205969, 375348199, 533768154, 81592791, 928765001, 702345552,
982979241, 459499478, 763042757, 126686003, 552985958, 482750359, 818718622, 748484428, 708268589, 648794433,
473905699, 647582466, 770158948, 397157026, 961471182, 358826159, 297046870, 699642581, 888948000, 440683007,
521062778, 130770701, 520223939, 211521658, 899648525, 833235135, 636577900, 179224151, 339483581, 955269534,
706092177, 24748204, 965866179, 311613056, 833814194, 176369778, 370197753, 103011921, 645941381, 823109475,
244702026, 446083030, 883734438, 363945461, 255830208, 628672405, 193846527, 111325803, 689914060, 398875936,
625238181, 522966817, 5906822, 561284876, 941250331, 788336779, 820701656, 833734278, 852037710, 576683781,
36551254, 82490363, 776643660, 823767907, 522479617, 470805974, 801058154, 429059615, 317287290, 28373308,
156669444, 369535646, 820005077, 966349005, 17425595, 601871796, 344822813, 450093249, 43011813, 182753917,
365808458, 173287449, 975748074, 896467879, 816982178, 140824878, 956121017, 146854490, 991656048, 279369914,
600027588, 190213014, 477766519, 995297939, 192626396, 622852686, 348388433, 837517092, 994516811, 539845621,
306653137, 215901575, 74092752, 85378281, 259149972, 141941182, 478024722, 244259025, 972194731, 721420118,
304432708, 534777820, 710566197, 700216698, 781660848, 499316348, 902395596, 551269912, 122829563, 899620761,
42408607, 130778020, 267328015, 537603777, 720559481, 772174292, 740079703, 419418968, 149102240, 950468464,
941507049, 960705655, 328042283, 107953050, 412460424, 942509934, 744657612, 884367732, 818170107, 508992613,
174295590, 258435637, 800618410, 439541821, 210632622, 318599551, 257366743, 112254316, 593205846, 337414888,
821861221, 59215144, 928196581, 796439573, 386885760, 644540454, 620416951, 885640438, 176695075, 575842112,
430679625, 683424291, 964059908, 535495714, 346521303, 66145163, 321162832, 26966819, 80257910, 352567893,
606762953, 326757128, 936438254, 493689268, 330177705, 548497940, 103064084, 987717118, 409889108, 476642393,
300076332, 990026161, 957603752, 279575203, 796141463, 430237782, 388412904, 914557304, 66398603, 419108079,
564739483, 360277144, 833370810, 793163343, 77555321, 459720549, 331852100, 870458104, 980273490, 406844238,
782707113, 625438948, 625279668, 481259993, 680191665, 390376751, 817287968, 329858310, 282230752, 250907860,
374236023, 313034982, 463415697, 622907436, 666586592, 451750478, 730276932, 371013370, 456813292, 904847358,
833818010, 332155020, 529792504, 311749609, 91093636, 793001596, 112262142, 950155165, 442268563, 586364148,
890744722, 378745118, 417531072, 348309723, 905741085, 674560685, 842495816, 478699582, 273295856, 623924882,
651503183, 260801639, 929792563, 570120042, 827395507, 377875481, 409778880, 254865961, 377370235, 603629622,
489235240, 708757527, 631945509, 106393814, 655044539, 540523391, 24746001, 448628979, 30453128, 917523298,
654354517, 835283546, 420232474, 781568290, 679088875, 310939466, 13418200, 175669958, 352628310, 159439479,
322651599, 973805882, 528339253, 360787657, 375391661, 171647216, 757806674, 557536089, 382163354, 831564544,
993118007, 590429555, 513990657, 238959287, 235625864, 726064841, 740374275, 910521402, 6011372, 796798874,
640854564, 362691708, 28269056, 552405639, 827754295, 324883111, 253656191, 411745874, 916352411, 821617329,
325454308, 806095418, 879753666, 86822057, 803226698, 817325532, 435364603, 605335068, 672227740, 941122665,
740201925, 692424682, 787635121, 575980237, 122392875, 768836805, 525855163, 692297897, 416003183, 709392402,
709206520, 369460428, 580925065, 901822521, 160582874, 903953869, 816717404, 515847646, 201117415, 362018594,
278191305, 910516143, 321783859, 554552090, 287020070, 944479569, 455267282, 665381735, 206313038, 3064210,
325776338, 522599769, 928844280, 273628329, 962068420, 653471535, 794286560, 157512688, 495719215, 448511035,
798686887, 581226982, 267792698, 50620045, 926275063, 673258316, 85790002, 69455051, 92792365, 260690128,
566944151, 376676829, 262517915, 97006512, 216334503, 122558827, 815783758, 7491383, 435669107, 594402063,
585335080, 200308901, 254307867, 623408278, 101584531, 638749265, 213822733, 574927059, 353380567, 908062966,
438001563, 956535097, 557189227, 168323628, 946320051, 600228771, 843452872, 394931229, 294479675, 679259740,
726660354, 789873018, 236408406, 46354911, 359477590, 764921787, 31421023, 832683365, 377639624, 266070748,
150097868, 702863446, 881824289, 761307806, 523963062, 316969153, 156637945, 478522591, 129518749, 637186672,
183004245, 434886008, 134834657, 726075096, 541779283, 417184133, 991486034, 333450250, 19049240, 655388726,
884136736, 623418196, 522422556, 510611863, 765373671, 484538332, 885044951, 677315717, 775337123, 665612125,
804493962, 223379614, 698348588, 369372909, 97424508, 80722496, 169028626, 503967942, 873647467, 742269751,
778760444, 233358696, 140037546, 489553189, 261780957, 614723289, 339198539, 143515523, 69141904, 454438360,
464165491, 757396683, 45354236, 520691312, 861326712, 816641656, 978083627, 313056924, 566092411, 754476393,
909750501, 470321615, 900387754, 588995960, 84350539, 209459107, 624527679, 671610616, 607393265, 297698676,
137623511, 419287093, 287724738, 959399556, 581333666, 754316716, 429822404, 549169627, 478442864, 367972293,
496002356, 948521882, 921015644, 582549666, 645172896, 175915527, 639517871, 260430783, 929534990, 793092840,
579793527, 312300806, 369657329, 712828952, 223143249, 245302915, 450372967, 437253970, 714824008, 571989253,
891339454, 542008010, 653542156, 918658026, 275425895, 565117033, 414620805, 553138750, 277789800, 770594228,
195125948, 624115475, 883251205, 34848122, 173720013, 936840881, 721277277, 38503524, 38164678, 563954134,
283484617, 719504594, 778921963, 445190187, 389795454
};

---

## a937: 嗟！

### #0 爆開算 $O(1)$

直接把階乘算出來，算$0$的個數

### #1 影片中的演算法 $O(log_5n)$

有認真點進去影片的，就知道裡面就有解法了
用$LL$存然後一直除$5$再加到$ans$
最後輸出$ans$即可

### #2 string 大數 $O(log_5n*n)$

跟 #1 一樣只是用`string`大數
除法就用長除法的方式去做
不然也可以`*2/10`，`/10`就直接去掉後面一位就可以了

### #3 LL array 大數 $O(log_5n*n)$

跟 #2 一樣只是用`LL array`存大數
一格存`19`位的數字
除法就用多項式除法的方式去做，或一樣`*2/10`

#include<bits/stdc++.h>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define pLL pair<LL, LL>
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
#define LL lolita
#define lolita long long
using namespace std;

void init();

const LL mod = 1e9 + 7, inf = numeric_limits<LL>::max(), maxN = 1e18;

LL arr[100];

bool check() {
    for(auto &i : arr) {
        if(i)
            return 1;
    }
    return 0;
}

void db5() {
    LL pass = 0;
    for(auto &i : arr) {
        i = i * 2 + pass, pass = 0;
        if(i / maxN)
            i -= maxN, pass = 1;
    }
    arr[0] /= 10;
    for(LL i = 1; i < 60; i ++ ) {
        arr[i - 1] += maxN / 10 * (arr[i] % 10);
        arr[i] /= 10;
    }
}

void solve() {
    string str;
    cin >> str;
    LL len = str.length();
    for(LL i = 0; ; i ++ ) {
        bool bln = 0;
        LL p = len - 18 * (i+1), k = 18;
        if(p < 0)
            k += p, p = 0, bln = 1;
        string tmp = str.substr(p, k);
        arr[i] = atoll(tmp.c_str());
        if(bln)
            break;
    }
    LL ans[100];
    memset(ans, 0, sizeof(ans));
    while(check()) {
        db5();
        LL pass = 0;
        for(LL i = 0; i < 100; i ++ ) {
            ans[i] += arr[i] + pass, pass = 0;
            if(ans[i] / maxN)
                ans[i] -= maxN, pass = 1;
        }
    }
    bool bln = 1;
    for(LL i = 99; i >= 0; i -- ) {
        string tmp = to_string(ans[i]);
        if(!bln) {
            while(tmp.length() != 18)
                tmp = '0' + tmp;
        }
        if(ans[i])
            bln = 0;
        if(bln && ans[i] == 0)
            continue;
        cout << tmp;
    }
    if(bln)
        cout << 0;
    cout << endl;
}

int main() {
    // IO;
    LL T;
    cin >> T;
    while(T -- )
        solve();
}

void init() {

}