因為世界并不如你想象的那樣壞。
寫在前面
期望得分：\(100+100+20 \sim 100 = 220 \sim 300pts\)
實際得分：\(100+0+30 = 130pts\) （因為教師機上的 lemon 不能用 lower_bound，這太傻逼了）
實際得分：\(100+100+30=230pts\) （換了台能用的機子，結果 2e8 沒跑過去，這太傻逼了）
洛谷得分：\(100+100+100=300pts\) （把資料點扔洛谷上，啪的一下就過了，我 AK 了？！）
T1 是個樹剖求 LCA 的闆子， 10min 切掉，然後花了 10min 想了幾種很怪的情況特判了；
然後開 T2，一眼是期望，用了 10min 想到一個不錯的思路，感覺很可做，20min 寫出來了，過了樣例，稍微算了一下沒爆 longlong 就扔掉看 T3 了。
T3 一眼以為是一個數位 DP，教練的題怎麼天天考數位DP，設了個五維的狀态 \(f_{i,j,x,y,k}\)，發現連 \(20\%\) 的資料都開不下，并且不會轉移。然後就棄了發呆。中間上撤鎖吃了頓飯，感覺思路如泉水般湧現。回來稍微完善了一下就碼出來了，感覺自己阿克了，找 KnightL 的暴力拍了一下，發現 \(n\&1=1\) 時被 Hack 了，并且在本地機子和極限資料下代碼跑了 5s+，感覺要涼。經過一陣緊張的調碼環節後發現是自己式子推錯了，改過了被 Hack 的部分過了，但在極限資料下依舊跑的很慢mmp。
題目扔這兒，有興趣的可以爆切了：T1,T2,T3
題解寫的太拉了，是以我成為了新的題解 /cy
題解
T1
可以利用 dfs 序來求解，如果 \(a\) 是 \(b\) 的祖先，當且僅當 \(dfn_a \le dfn_b < dfn_a + siz_a\)，預處理 \(O(n)\)，查詢 \(O(1)\)。
也可以使用樹剖求 LCA 去判斷兩個點之間的關系，時間複雜度 \(O(n \log n)\)。
也可以倍增求 LCA，需要 \(O(n \log n)\) 的預處理，不過查詢的複雜度都是 \(O(\log n)\)。
反正随便過啦
/*
Work by: Suzt_ilymics
Problem: 不知名屑題
Knowledge: 垃圾算法
Time: O(能過)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
struct edge {
int to, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 1;
int n, m, rt;
int dep[MAXN], fath[MAXN], siz[MAXN], son[MAXN], top[MAXN];
bool vis[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void add_edge(int from, int to) { e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1, fath[u] = fa, siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
if(siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fath[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int Get_Lca(int x, int y) {
while(top[x] != top[y]) dep[top[x]] < dep[top[y]] ? y = fath[top[y]] : x = fath[top[x]];
return dep[x] < dep[y] ? x : y;
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = read();
for(int i = 1, u, v; i <= n; ++i) {
u = read(), v = read();
if(v == -1) rt = u;
else {
add_edge(u, v), add_edge(v, u);
vis[u] = vis[v] = true;
}
}
dfs(rt, 0), dfs2(rt, rt);
m = read();
for(int i = 1, u, v; i <= m; ++i) {
u = read(), v = read();
int lca = Get_Lca(u, v);
if(u == v || !vis[u] || !vis[v]) puts("0");
else if(lca == u) puts("1");
else if(lca == v) puts("2");
else puts("0");
}
return 0;
}
T2
考慮固定 \(A\) 序列，然後随便安排 \(B\) 的位置，顯然這依舊是合法的。方案數是全排列的方案數 \(n!\) 。
發現全排列不好枚舉，考慮計算所有可能下 \(a_i\) 與 \(b_j\) 的對決次數。
固定這兩個位置，其他的随便枚舉，是以對決次數為 \((n-1)!\)，是以這兩個人對 \(A\) 隊分數的貢獻為 \(\frac{(a_i - b_j)^2}{n} [a_i > b_j]\)。
然後枚舉所有 \(a_i\) 與所有 \(b_j\) 對決就是答案
\(B\) 隊同理。是以：
\[ansa = \sum_{i=1}^{n}\sum_{j=1 \&\& a_i > b_j}^n \frac{(a_i - b_j)^2}{n}
\]
\[ansb = \sum_{i=1}^{n}\sum_{j=1 \&\& b_i > a_j}^n \frac{(b_i - a_j)^2}{n}
這樣的複雜度是 \(O(n^2)\)，顯然過不掉。
發現排序對答案沒有影響，是以先對兩個數組排序。
用 \(lower\_bound\) 找到第一個比 \(a_i\) 大的點的位置 \(x\)，答案變為
\[ansa = \sum_{i=1}^{n}\sum_{j=1}^x \frac{(a_i - b_j)^2}{n}
然後把平方差拆開，發現可以預處理字首和，字首平方和。然後每個元素就可以 \(O(1)\) 算了。
總時間複雜度 \(O(n \log n)\) ，瓶頸在二分那，不過也能過了。
發現兩個隊都是單調的，是以每次二分找的位置一定是單調增的，可以用個指針，指針隻會向右移動，是以複雜度是 \(O(n)\) 的。
為了避免精度問題，可以最後除以 \(n\)，算一下開 longlong 是不會爆的。
代碼是使用 \(lower\_bound\) 的版本。
/*
Work by: Suzt_ilymics
Problem: 不知名屑題
Knowledge: 垃圾算法
Time: O(能過)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int n;
LL a[MAXN], b[MAXN];
LL suma[MAXN], sumb[MAXN];
LL suma2[MAXN], sumb2[MAXN];
LL ansa = 0, ansb = 0;
double Ans;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int main()
{
// freopen("mat.in","r",stdin);
// freopen("mat.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; ++i) suma[i] = suma[i - 1] + a[i];
for(int i = 1; i <= n; ++i) sumb[i] = sumb[i - 1] + b[i];
for(int i = 1; i <= n; ++i) suma2[i] = suma2[i - 1] + a[i] * a[i];
for(int i = 1; i <= n; ++i) sumb2[i] = sumb2[i - 1] + b[i] * b[i];
for(int i = 1; i <= n; ++i) {
int wz = lower_bound(b + 1, b + n + 1, a[i]) - b - 1;
ansa += wz * a[i] * a[i] - 2 * a[i] * sumb[wz] + sumb2[wz];
}
for(int i = 1; i <= n; ++i) {
int wz = lower_bound(a + 1, a + n + 1, b[i]) - a - 1;
ansb += wz * b[i] * b[i] - 2 * b[i] * suma[wz] + suma2[wz];
}
ansa -= ansb;
Ans = (double)ansa / n;
printf("%.1f", Ans);
return 0;
}
T3
可以設個五維的狀态 \(f_{i,j,x,y,k}\) 分别表示 目前位數，上一次填的數，總和，前 \(n\) 個數的和，奇數位的和 然後數位 DP。發現空間在 \(20 \%\) 的資料下都開不下，笑死。
考慮換個思路，設 \(f_{i,j}\) 表示填了 \(i\) 位，總和為 \(j\) 的方案數。
如何求 \(f_{i,j}\)？
把它當做一個 01背包 ，一共 \(|S|\) 件物品選 \(n\) 次（為什麼隻需要算到 \(n\) 到後面就自然明白）。
初始化 \(|S|\) 中的每個元素 \(x\) 選一次都是 \(1\)，即 \(f_{1,x} = 1\)。
考慮隻有前 \(n\) 個數和後 \(n\) 個數和相同的情況。利用乘法原理，總方案數為：
\[\sum_{x=0}^{Max}f_{n,x}^2
其中 \(Max\) 表示所填的數的和的上限。
在考慮第二個限制，發現和第一個限制一樣都是填兩次 \(n\) 個數，然後兩次和相同，隻不過填的位置換了換。
是以在上面的基礎上 \(\times 2\) 即可。
同時滿足的情況重複計算了，考慮如何篩去。同時考慮兩個條件的性質應該不難想。
設 \(k = n / 2\) 表示前面 \(n\) 個數中有幾個偶數位，設 \(x\) 表示前 \(n\) 個數中的偶數位和為 \(x\)，設前 \(n\) 數總和為 \(s\)。其方案數可以用 \(f_{k,x}\) 表示。
那麼，前 \(n\) 個數中有 \(n-k\) 個奇數位，奇數位的和為 \(k-x\)，方案數為 \(f_{n-k,s-x}\)
同理，後 \(n\) 個數中奇數位的情況應當與前 \(n\) 個數中偶數位的情況相同，後 \(n\) 個數中偶數位的情況應當與前 \(n\) 個數中奇數位的情況相同，方案數分别為 \(f_{k,x},f_{n-k,s-x}\)。
利用乘法原理，要減去的總的貢獻為
\[\sum_{s=0}^{Max}\sum_{x=0}^{s} f_{k,x}^2 \times f_{n-k,s-x}^2
極限情況下複雜度為 \(O(10^8)\)，正常評測機是可以過的，但學校的古董機過不去。
我們發現，前 \(n\) 個數奇數位填的數隻和後 \(n\) 個數偶數位填的數相關。與另外兩個無關。是以考慮把兩部分先單獨算出來在用乘法原理。
設 \(Max1,Max0\) 分别表示前 \(n\) 個數奇數位填的最大位數和和偶數位填的最大位數和。
要減去的總的方案數為
\[(\sum_{x=0}^{Max0}f_{k,x}^2) \times (\sum_{y=0}^{Max1} f_{n-k,y})
減去即可。
複雜度為 \(O(Max0+Max1)\)。你會發現預處理極限情況下依舊是 \(O(10^8)\)
/*
Work by: Suzt_ilymics
Problem: 不知名屑題
Knowledge: 垃圾算法
Time: O(能過)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 999983;
char s[11];
int n, Ans = 0, sum = 0, k;
int stc[11], sc = 0;
int f[1010][10010];
//int sum[10010], sum2[10010];
// f[i][j] 表示填了 i 位，總和為 j 的方案數
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
signed main()
{
// freopen("num.in","r",stdin);
// freopen("num.out","w",stdout);
n = read(); k = n / 2;
cin >> s + 1;
int len = strlen(s + 1);
for(int i = 1; i <= len; ++i) {
stc[++sc] = s[i] - '0'; // 其實這個行為挺傻逼的
f[1][stc[sc]] = 1;
}
if(n == 1) {
cout<<sc<<endl;
return 0;
}
if(sc == 1) {
puts("1");
return 0;
}
sort(stc + 1, stc + sc + 1);
int Max = n * stc[sc];
for(int i = 2; i <= n; ++i) {
for(int k = Max; k >= 0; --k) {
for(int j = 1; j <= sc; ++j) {
f[i][k] = f[i][k] + f[i-1][k - stc[j]];
if(f[i][k] > mod) f[i][k] -= mod;
}
}
}
for(int i = 0; i <= Max; ++i) {
Ans = Ans + f[n][i] * f[n][i] % mod;
if(Ans > mod) Ans -= mod;
}
Ans = Ans * 2 % mod;
// cout<<Ans<<endl;
for(int i = 0; i <= Max; ++i) {
for(int j = 0; j <= i; ++j) {
// sum = f[k][j] * f[n-k][i-j] * f[n-k][i-j] % mod;
// sum = sum * f[k][j] % mod;
// cout<<"前 n 個偶數： "<<k<<" 前 n 個奇數："<<n-k<<" 前n個數和："<<i<<" 偶數占的和："<<j<<"\n";
// cout<<f[k][j]<<" "<<f[n-k][i-j]<<" "<<f[n-k][i-j]<<" "<<f[k][j]<<"\n";
// cout<<i<<" "<<j<<" "<<sum<<endl;
// Ans -= sum;
// cout<<i<<" "<<j<<endl;
Ans = (Ans - f[k][j] * f[n - k][i-j] % mod * f[n-k][i-j] % mod * f[k][j] % mod) % mod;
// 前n個的偶數 前 n 個的奇數 後 n 個的偶數 後 n 個的奇數
}
}
Ans = (Ans + mod) % mod;
cout<<Ans<<endl;
// for(int i = 0; i <= 6;++i) {
// for(int j = 0; j <= 8; ++j) {
// cout<<f[i][j]<<" ";
// }puts("");
// }
return 0;
}