廣二聯考題解補全計劃：
第十六套
T1：構造
T2：觀察性質，DP
T3: bitset 優化DP，狀態設計
T4: 平衡樹動態維護歐拉序
-
T1:
簡單的構造題，發現性質就很簡單，自己當時還因為技術問題卡了2個小時，這導致后面時間不夠，提升T1做題速度，別被簽到卡了 -
T4:
平衡樹動態維護歐拉序，之前單獨加訓過，不管 -
T3:
觀察到式子重復性很高
$ f_{i+1,j+1}|=f_{i,j} \ \ \ \ \ \ \ \ \ s_i=t_j$
$ f_{i,j+2}|=f_{i,j} \ \ \ \ \ \ \ \ \ \ \ t_{j+1}=t_{j+2}$
我們考慮這個特殊的配對，枚舉j,把 \(f_i\) 塞到bitset里，如果 \(t_{j+1}=t_{j+2}\) 那么把j 的bitset拉過來，提前處理好字符的bitset，就可以了 -
T2:
考慮第一問答案肯定是 \(maxdep\),經過簡單證明我們發現能動這個點當且僅當子樹外沒有深度大于等于他的點。
于是我們可以只操作長鏈。
于是我們可以處理每個點能操作的時間區間
于是我們設計狀態 \(f_{l,r,j}\) 表示l,r這段長鏈獨立出來，l及其祖先操作了j次，轉移分開轉移，是一個記搜形式，也可以倒著DP
\(f_{l,r,j}=f_{l,r-1,j+1}\)
$f_{l,r,j}=f_{l,p-1,j} \times f_{p,r-1,j+1} \times \binom{r-l}{p-l} $
第十七套：
T1：取模性質，倍增
T2: DP優化，狀態優化
T3：容斥原理，數位DP
T4：不會，神秘可持久化平衡樹，WBLT
T1:
首先先提一個關于取模的性質，一個數對一個比它小的數取模，大小一定減半，考慮對 $ \frac {n}{2}$ 分治即可。
我們先預處理出來每個數后面第一個比他小的位置，這樣形成一個樹形結構。
根據前面的性質，有：
\(S_p(x) = \lfloor \dfrac{x}{a_q} \rfloor S_q(a_q-1) + S_q(x \bmod a_q)\)，預處理出 \(S_p(a_p-1)\) 就可以做到只處理log次，每次還需要樹上倍增找下一個比他小的，那么兩只log即可快速查詢
T2：
萌熊原題，寫一下思考過程：
-
因為只關心英雄集合，我們貪心地讓所選英雄集合去對抗盡可能小的
怪獸 -
于是 \(n^{3}\) 式子很好想，我們枚舉集合大小 $k $ ,那么設計 \(f_{i,j}\) 枚舉到第i個英雄，贏了j場，轉移就不寫了
-
優化前途在于枚舉狀態，我們發現我們 \(k\) 是必須要枚舉的，前面設計的狀態如果我們要求英雄輸就很不好處理，我們考慮前后兩端枚舉，前面枚舉贏的集合，后面枚舉輸的集合，最后再拼起來
-
發現不能直接拼，我們找到這樣一個位置 \(a_k < b_p < a_{k+1}\)，這樣我們發現前面沒贏的都能在后面輸，后面沒輸的都能在前面贏。在這個位置拼起來就行了
T3：
UNR好題
之前學容斥有一個式子是 $ x_i \le b_i \ \ \ 求 \sum x_i=m$ 的方案數，那我們容斥做就好了
這個題是小于等于，那我們新加一個盒子，表示在這個盒子里的我們扔掉。
設 $ A=n+m+k(c-1) $,把后面那一坨拆拆，得到一個下降冪形式,把它看做多項式：
拆一下系數，有
下面你要求后面那一坨 \(b^i\) 的和
設計 \(f_{i,j,k}\) 表示第 i 位 目前集合大小為j,\(x^k\)前面的系數：
注意到上面下降冪式子只有在為初始值為正時有意義，數位DP一下頂沒頂上界即可
點擊查看代碼
int Ans=0;
for(int K=0;K<=m;K++) {
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
int A=(Nm+m+K*(c-1)%P)%P;
g[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=m;j++) {
g[i][j]=g[i-1][j]*(A-i+1)%P;
if(j) g[i][j]=(g[i][j]-g[i-1][j-1])%P;
}
vector<int > B=n+m+K*(c-1);
if(B[0]<0) continue;
while(B.size()<=m) B.push_back(0);
int mx=0;
for(int i=m+1;i<B.size();i++) mx=max(mx,B[i]);
if(mx) f[m+1][0][0][0]=1;
else f[m+1][0][0][1]=1;
for(int i=m;i>=1;i--)
for(int j=0;j<=K;j++) {
for(int z=0;z<=m;z++) {
if(B[i]>1) {
f[i][j][z][0]=(f[i+1][j][z][1]+f[i+1][j][z][0])%P;
if(!j) continue;
for(int w=0;w<=z;w++) {
int zy=f[i+1][j-1][w][0]+f[i+1][j-1][w][1],xs=pw[i*(z-w)];
f[i][j][z][0]=(f[i][j][z][0]+C[z][w]*zy%P*xs)%P;
}
}
else if(B[i]==1) {
f[i][j][z][0]=(f[i+1][j][z][1]+f[i+1][j][z][0])%P;
if(!j) continue;
for(int w=0;w<=z;w++) {
int zy=f[i+1][j-1][w][0],xs=pw[i*(z-w)];
f[i][j][z][0]=(f[i][j][z][0]+C[z][w]*zy%P*xs)%P;
zy=f[i+1][j-1][w][1];
f[i][j][z][1]=(f[i][j][z][1]+C[z][w]*zy%P*xs)%P;
}
}
else {
f[i][j][z][0]=f[i+1][j][z][0];
f[i][j][z][1]=f[i+1][j][z][1];
for(int w=0;w<=z;w++) {
int zy=f[i+1][j-1][w][0],xs=pw[i*(z-w)];
f[i][j][z][0]=(f[i][j][z][0]+C[z][w]*zy%P*xs)%P;
}
}
}
}
int res=0;
for(int i=0;i<=m;i++) res=(res+(f[1][K][i][0]+f[1][K][i][1])*g[m][i]%P)%P;
if(K&1) res=-res;
Ans=(Ans+res+P)%P;
}
田安源題目：
T1矩陣乘法板子，T2哈希板子，T3:單調隊列優化DP,T4:分塊
T3:設計 \(f_i=f_j+1\) ，\(f_i\) 代表這個位置必須選
設 \(L_i\) 表示不包括i的區間l最靠右的位置，因為不能漏區間不選
\(R_i\) 表示包括i 的區間l最靠左的位置，因為不能重復選
特殊處理一下，L取前綴max,R取后綴min，O（n）求一下
單調隊列維護即可
有使用數學歸納法不用單調隊列的，這里不提
T4: 場切，水題，b 的值域很小，發現 a 也可以取模，那么兩個相鄰的數貢獻的a是一些區間，分塊去做就可以
浙公網安備 33010602011771號