快樂(lè )的CSP-S前最后一場(chǎng)賽擬模
1
給出 \(n,m,c\) 和長(cháng)度分別為 \(n,m\) 的序列 \(a,b\)，有 \(t\) 次詢(xún)問(wèn)，每次詢(xún)問(wèn)給出 \(p,q\)，求 \(\sum_{i=1} ^n \sum_{j=1} ^m [i\times p+j\times q=c]\times a_i \times b_j\)。
簡(jiǎn)單根號分治，可以很簡(jiǎn)單的做到 \(O(c\sqrt c)\) 的復雜度，不過(guò)賽時(shí)好像一車(chē)人寫(xiě)得 \(O(c^\frac53)\) 還賴(lài)卡常？不理解，但不反駁。
容易想到按照 \(\max\{p,q\}\) 分治，對于 \(\max\{p,q\}\) 較小的部分，預處理出兩個(gè)數組 \(sum1,sum2\)，分別代表 \(p,q\)，和 \(q,p\) 的值，且人為規定讓后一項小于前一項，這樣子的話(huà)預處理就會(huì )長(cháng)成下面的樣子：
for(int p = 1; p <= 548; p ++) {for(int x = 1; x <= n and x * p <= c; x ++) {int qy = c - x * p;for(int q = 1; q <= p; q ++) {if(qy % q == 0) {int y = qy / q;if(y <= m)(sum1[p][q] += (a[x] * b[y]) % mod) %= mod;}}}}for(int q = 1; q <= 548; q ++) {for(int y = 1; y <= m and y * q <= c; y ++) {int px = c - q * y;for(int p = 1; p <= q; p ++) {if(px % p == 0) {int x = px / p;if(x <= n)(sum2[q][p] += (a[x] * b[y] % mod)) %= mod;}}}}
看起來(lái)很丑陋，三層循環(huán)，好像是 \(O(B^2C) = O(C^2)\) 的東西，實(shí)際上后兩層層是 \(O(\frac Cp \times p) = O(C)\) 的，所以三層一共是 \(O(CB) = O(C\sqrt C)\) 的。
然后比較大的部分就暴力就完了，很簡(jiǎn)單的。
2
是不會(huì )的 SOS DP。非常美麗的東西，賽時(shí)寫(xiě)了 \(O(n2^m)\) 的惡心東西。然后就，改改吧。。。
快考試了你讓我學(xué)新東西？？？？？
快考試了你讓我學(xué)新東西？？？？？
快考試了你讓我學(xué)新東西？？？？？
快考試了你讓我學(xué)新東西？？？？？
快考試了你讓我學(xué)新東西？？？？？
快考試了你讓我學(xué)新東西？？？？？
不學(xué)，放了。
3
好神秘的東西，觀(guān)察出來(lái)了神秘性質(zhì)，但是沒(méi)有寫(xiě)出來(lái)單調隊列優(yōu)化 DP 和什么并查集建圖。。。人話(huà)就是打了個(gè)暴力。
是 \(O(Tnmq)\) 的暴力，但是和 \(O(Tn^2m^2q)\) 是一個(gè)分，難繃。
4
沒(méi)打出暴力、