20231215
NOIP2022 sol + 4道杂题
A. [NOIP2022] 种花
小 C 决定在他的花园里种出 \(\texttt{CCF}\) 字样的图案，因此他想知道 \(\texttt C\) 和 \(\texttt F\) 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。
花园可以看作有 \(n\times m\) 个位置的网格图，从上到下分别为第 \(1\) 到第 \(n\) 行，从左到右分别为第 \(1\) 列到第 \(m\) 列，其中每个位置有可能是土坑，也有可能不是，可以用 \(a_{i,j} = 1\) 表示第 \(i\) 行第 \(j\) 列这个位置有土坑，否则用 \(a_{i,j} = 0\) 表示这个位置没土坑。
一种种花方案被称为 \(\texttt{C-}\) 形的，如果存在 \(x_1, x_2 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_2\) 行都不为土坑，且只在上述这些位置上种花。
一种种花方案被称为 \(\texttt{F-}\) 形的，如果存在 \(x_1, x_2, x_3 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2 < x_3\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_3\) 行都不为土坑，且只在上述这些位置上种花。
样例一解释中给出了 \(\texttt{C-}\) 形和 \(\texttt{F-}\) 形种花方案的图案示例。
现在小 C 想知道，给定 \(n, m\) 以及表示每个位置是否为土坑的值 \(\{a_{i,j}\}\)，\(\texttt{C-}\) 形和 \(\texttt{F-}\) 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 \(998244353\) 取模的结果即可，具体输出结果请看输出格式部分。
\(1 \leq T \leq 5\)，\(1 \leq n, m \leq 10^3\)，\(0 \leq c, f \leq 1\)，\(a_{i,j} \in \{0, 1\}\)。
直接模拟即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+5;
const ll mod=998244353;
int nw,n,m,c,f,s[N][N],sc[N],sf[N],T,id;
ll ansc=0,ansf=0;
char a[N][N];
int main(){
/*2023.12.15 H_W_Y P8865 [NOIP2022] 种花 乱搞*/
scanf("%d%d",&T,&id);
while(T--){
scanf("%d%d%d%d",&n,&m,&c,&f);
memset(s,0,sizeof(s));
memset(sc,0,sizeof(sc));
memset(sf,0,sizeof(sf));
ansc=ansf=0;
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
for(int j=m;j>=1;j--){
if(a[i][j]=='0') s[i][j]=s[i][j+1]+1;
else s[i][j]=0;
}
}
for(int j=1;j<=m;nw=0,j++){
for(int i=n;i>=1;i--){
if(a[i][j]=='0') sc[i]=sc[i+1]+s[i][j]-1,sf[i]=sf[i+1]+(s[i][j]-1)*nw,++nw;
else nw=0,sc[i]=sf[i]=0;
}
for(int i=1;i+2<=n;i++){
if(a[i][j]=='1'||a[i+1][j]=='1') continue;
ansc=(ansc+1ll*(s[i][j]-1)*sc[i+2]%mod)%mod;
ansf=(ansf+1ll*(s[i][j]-1)*sf[i+2]%mod)%mod;
}
}
ansc*=c;ansf*=f;
printf("%lld %lld\n",ansc,ansf);
}
return 0;
}
B. [NOIP2022] 喵了个喵
小 E 喜欢上了一款叫做《喵了个喵》的游戏。这个游戏有一个牌堆和 \(n\) 个可以从栈底删除元素的栈，任务是要通过游戏规则将所有的卡牌消去。开始时牌堆中有 \(m\) 张卡牌，从上到下的图案分别是 \(a_1, a_2,\dots, a_m\)。所有的卡牌一共有 \(k\) 种图案，从 \(1\) 到 \(k\) 编号。牌堆中每一种图案的卡牌都有偶数张。开始时所有的栈都是空的。这个游戏有两种操作：
- 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。
- 选择两个不同的栈，如果这两个栈栈底的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。
这个游戏一共有 \(T\) 关，小 E 一直无法通关。请你帮小 E 设计一下游戏方案，即对于游戏的每一关，给出相应的操作序列使得小 E 可以把所有的卡牌消去。
测试点 \(T=\) \(n\) \(k=\) \(m \leq\) \(1\sim 3\) \(1001\) \(\leq 300\) \(2n-2\) 无限制 \(4\sim 6\) \(1002\) \(=2\) \(2n-1\) 无限制 \(7\sim 10\) \(3\) \(=3\) \(2n-1\) \(14\) \(11\sim 14\) \(1004\) \(=3\) \(2n-1\) 无限制 \(15\sim 20\) \(1005\) \(\leq 300\) \(2n-1\) 无限制
这个表挺有意思的啊。好一道构造题。
首先，容易发现我们的 \(k\) 只有两种取值，为什么呢？
因为小了太简单了，而大了根本做不了，
所以我们不妨从 \(k=2n-2\) 这个最小的入手。
发现这种情况是简单的，也就是我们将前 \(n-1\) 个栈，一个栈放两个，
上面一个下面一个，容易证明，每一种只有一个。
那么这样我们会多出来一个栈，我们把它叫做 特殊栈，
发现有了这个栈之后就很好处理了。
假设当前进来一个 \(i\) 种类的，
如果它之前没有出现过，那么直接放到一个有空位的栈里面去就可以了。
而如果它在一个栈的上面，我们直接放上去抵消掉即可，
反之我们就把它放在 特殊栈 里面，利用特殊栈把它消掉。
这样问题就可以轻松解决。
现在再来考虑多一个的情况，
那么它也一定是把所有的栈都满了的时候才会出现。
假设现在已经放满了，当前又进来了一个新的种类 \(w\)，我们希望知道他能放在哪里？
首先需要找到下一个栈底元素进来的位置，因为这个时候消掉那个栈底元素会用到特殊栈，
我们假设这个栈是 \([v,u]\) 表示它上面是 \(v\)，下面是 \(u\)，那么这个 \(w\) 的位置只会影响到这一个栈，因为 \(u\) 下一个出现最早。
于是有以下几种情况：
- 下一个 \(w\) 在下一个 \(u\) 之前，那么这个特殊栈随便用，之间把 \(w\) 放到特殊栈里面去。
- \(u \lt v \lt w\)，即下一个 \(u\) 最先出现（这里的 \(\lt\) 是下一个的出现时间），那么我们直接把 \(w\) 叠在 \(v\) 上面，因为 \(u\) 很快就会走了。
- \(v \lt u \lt w\)，那么我们不能把 \(w\) 放到 \(v\) 上面，因为 \(v\) 很快就要走了，而在 \(u\) 出现之前我们又不会用到特殊栈，所以我们直接把 \(w\) 放到特殊栈里面。于是这个时候就出现了一个 换栈 的过程，即全局的特殊栈现在变成了 \([v,u]\) 所在的栈，容易发现这样不会错。
这样我们就分析完了，具体实现的时候也就是直接模拟，
找下一个出现位置也可以直接找，因为我们一定不会重复找一段区间。
我们直接维护一下特殊栈是哪个栈，那些栈有空位即可。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int M=2e6+5;
int n,m,k,a[M],h[605],pos,T;
vector<deque<int> > s(305);
struct node{int op,x,y;};
vector<node> ans;
queue<int> q;
void init(){
for(int i=1;i<=k;i++) h[i]=0;
while(!q.empty()) q.pop();
ans.clear();pos=0;
}
void oper1(int x,int v){
ans.pb((node){1,x,0});
if(s[x].size()&&s[x].back()==v){
s[x].pop_back();
if(x!=pos&&s[x].size()<2) q.push(x);
h[v]=0;
}else s[x].pb(v),h[v]=x;
}
void oper2(int x,int y){
ans.pb((node){2,x,y});
h[s[x][0]]=0;
s[x].pop_front();s[y].pop_front();
if(x!=pos&&s[x].size()<2) q.push(x);
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*2023.12.15 H_W_Y P8866 [NOIP2022] 喵了个喵 构造*/
cin>>T;
while(T--){
cin>>n>>m>>k;
init();
for(int i=1;i<=m;i++) cin>>a[i];
pos=n;
for(int i=1;i<n;i++) q.push(i),q.push(i);
for(int i=1;i<=m;i++){
int x=h[a[i]];
if(x){
if(s[x].back()==a[i]) oper1(x,a[i]);
else oper1(pos,a[i]),oper2(x,pos);
continue;
}
if(!q.empty()){
x=q.front();q.pop();
oper1(x,a[i]);
continue;
}
for(int j=i+1;j<=m;j++){
if(a[j]==a[i]) break;
else if(h[a[j]]&&s[h[a[j]]][0]==a[j]){x=h[a[j]];break;}
}
if(x==0) oper1(pos,a[i]);
else{
int fi=s[x].front(),se=s[x].back();
for(int j=i+1;j<=m;j++){
if(a[j]==fi){oper1(x,a[i]);break;}
else if(a[j]==se){
oper1(pos,a[i]);q.push(pos);
pos=x;break;
}
}
}
}
cout<<ans.size()<<'\n';
for(auto i:ans){
if(i.op==1) cout<<1<<" "<<i.x<<'\n';
else cout<<2<<' '<<i.x<<' '<<i.y<<'\n';
}
}
return 0;
}
C. [NOIP2022] 建造军营
A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。
A 国的国土由 \(n\) 座城市组成，\(m\) 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。
众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。
A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 \(1,000,000,007\left(10^{9}+7\right)\) 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。
\(1 \leq n \leq 5 \times 10^5\)，\(n - 1 \leq m \leq 10^6\)，\(1 \leq u_i, v_i \leq n\)，\(u_i \neq v_i\)。
首先，很容易发现，这个东西就是让你先缩点，留下来桥的。
于是我们就得到了一棵树，
这些树边的选择是有要求的，而每一个边双里面的边是可选可不选的，也就是有 \(2^{a_u}\) 种情况，
而这里的 \(a_u\) 是一个边双的大小。
剩下来的这个计数问题就变成了一个树形 dp 了，
发现选不选桥其实只是和你选没选这个子树中的节点有关，于是我们记 \(f_u\) 表示选了 \(u\) 子树中的点的方案数，
记录答案的时候就是你选的这些点的 LCA 是 \(u\) 的情况对答案的贡献。
而这个转移是平凡的，
直接枚举一下 \(v\) 加上答案，而注意要排除一个都没选的情况，记录答案的时候要减去 LCA 不是 \(u\) 的贡献。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const ll mod=1e9+7;
const int N=1e6+5;
int n,m,sz[N],a[N],bl[N],scc=0,st[N<<2],tp=0,dfn[N],low[N],idx=0;
ll f[N],t[N],ans=0;
vector<int> G[N];
vector<pii> g[N];
void tarjan(int u,int k){
dfn[u]=low[u]=++idx;st[++tp]=u;
for(auto i:g[u]){
int v=i.fi;
if(!dfn[v]) tarjan(v,i.se),low[u]=min(low[u],low[v]);
else if(i.se!=k) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
++scc;int x;
while((x=st[tp])){
bl[x]=scc;--tp;
if(x==u) break;
}
}
}
void init(){
t[0]=1ll;
for(int i=1;i<N;i++) t[i]=(t[i-1]+t[i-1])%mod;
}
void dfs(int u,int fa){
sz[u]=1;f[u]=t[a[u]];
for(auto v:G[u]){
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
f[u]=f[u]*(t[sz[v]]+f[v])%mod;
}
f[u]=(f[u]-t[sz[u]-1]+mod)%mod;
ll s=f[u];
for(auto v:G[u]){
if(v==fa) continue;
s=(s-f[v]*t[sz[u]-sz[v]-1]%mod+mod)%mod;
}
ans=(ans+s*t[scc-sz[u]]%mod)%mod;
}
int main(){
/*2023.12.20 H_W_Y P8867 [NOIP2022] 建造军营 Tarjan + 树形 dp*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;init();
for(int i=1,u,v;i<=m;i++) cin>>u>>v,g[u].pb({v,i}),g[v].pb({u,i});
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
for(int u=1;u<=n;u++){
++a[bl[u]];
for(auto i:g[u]){
int v=i.fi;
if(bl[v]!=bl[u]) G[bl[u]].pb(bl[v]);
}
}
dfs(1,0);
ans=ans*t[m-scc+1]%mod;
cout<<ans<<'\n';
return 0;
}
D. [NOIP2022] 比赛
给定 \(A_{1,2,\dots,n},B_{1,2,\dots,n}\)，以及 \(m\) 个询问，每次询问给出 \(l,r\)，求
\[\sum_{p=l}^r \sum_{q=p}^r (\max_{i=p}^q A_i)(\max_{i=p}^q B_i) \]\(1 \le n,m \le 2.5 \times 10^5\)。
区间子区间问题典。
区间子区间问题的常规处理方法已经在 lxlds 中讲的很清楚了，
这道题的 \(\max\) 我们同样可以用单调栈维护出来，分析一下去加信息累加时的标记。
其实题解部分已经讲得很清楚了
主要的思想就是先将同类的标记合并之后，我们对于交错的标记再进行一个讨论就可以了，
也就是分组，累加时分类讨论。具体看代码吧。
代码中我们钦定一个标记组是先历史值累加再赋值。
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int N=1e6+5;
int n,m,a[N],b[N],st[N],tp=0,fa[N],fb[N];
ull ans[N];
vector<pii> g[N];
struct tag{ull cx,cy,xy,x,y,c;}tg[N<<2];
struct sgt{
ull s,xy,x,y;
sgt operator +(const sgt &t)const{return (sgt){s+t.s,xy+t.xy,x+t.x,y+t.y};}
}tr[N<<2];
#define mid ((l+r)>>1)
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define lc p<<1
#define rc p<<1|1
void pu(int p){tr[p]=tr[lc]+tr[rc];}
/*先历史值累计再更新*/
void change(int l,int r,int p,tag t){
ull &cx=tg[p].cx,&cy=tg[p].cy,&xy=tg[p].xy,&x=tg[p].x,&y=tg[p].y,&c=tg[p].c;
int len=r-l+1;
if(cx&&cy) c+=t.xy*cx*cy+t.x*cx+t.y*cy+t.c;
else if(cx) y+=t.y+cx*t.xy,c+=cx*t.x+t.c;
else if(cy) x+=t.x+cy*t.xy,c+=cy*t.y+t.c;
else x+=t.x,y+=t.y,xy+=t.xy,c+=t.c;
if(t.cx) cx=t.cx;
if(t.cy) cy=t.cy;
ull &s=tr[p].s,&sxy=tr[p].xy,&sx=tr[p].x,&sy=tr[p].y;
s+=t.xy*sxy+t.x*sx+t.y*sy+1ull*t.c*len;
if(t.cx&&t.cy) sxy=t.cx*t.cy*len,sx=t.cx*len,sy=t.cy*len;
else if(t.cx) sxy=t.cx*sy,sx=t.cx*len;
else if(t.cy) sxy=t.cy*sx,sy=t.cy*len;
}
void pd(int l,int r,int p){
if(tg[p].cx||tg[p].cy||tg[p].x||tg[p].xy||tg[p].y||tg[p].c)
change(lson,tg[p]),change(rson,tg[p]),tg[p]=(tag){0,0,0,0,0,0};
}
void upd(int l,int r,int p,int x,int y,tag t){
if(x<=l&&y>=r) return change(l,r,p,t);pd(l,r,p);
if(x<=mid) upd(lson,x,y,t);
if(y>mid) upd(rson,x,y,t);pu(p);
}
ull qry(int l,int r,int p,int x,int y){
if(x<=l&&y>=r) return tr[p].s;pd(l,r,p);
if(y<=mid) return qry(lson,x,y);
if(x>mid) return qry(rson,x,y);
return qry(lson,x,y)+qry(rson,x,y);
}
int main(){
/*2023.11.30 H_W_Y P8868 [NOIP2022] 比赛 SGT*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
while(tp>0&&a[st[tp]]<a[i]) tp--;
fa[i]=st[tp]+1;st[++tp]=i;
}tp=0;
for(int i=1;i<=n;i++){
cin>>b[i];
while(tp>0&&b[st[tp]]<b[i]) tp--;
fb[i]=st[tp]+1;st[++tp]=i;
}
cin>>m;
for(int i=1,l,r;i<=m;i++) cin>>l>>r,g[r].pb({l,i});
for(int r=1;r<=n;r++){
upd(1,n,1,fa[r],r,(tag){1ull*a[r],0,0,0,0,0});
upd(1,n,1,fb[r],r,(tag){0,1ull*b[r],0,0,0,0});
upd(1,n,1,1,r,(tag){0,0,1,0,0,0});
for(auto j:g[r]) ans[j.se]=qry(1,n,1,j.fi,r);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}
E. 石老板郁郁寡欢 - LCM + GCD
石老板这几天一直郁郁寡欢，因为他无法解决如下数学题：
有 \(n\) 个正整数 \(a_i\)，并令它们的积为 \(S\)，即 \(S=a_1 \times a_2 \times a_3 \times \dots \times a_n\)。
这 \(n\) 个正整数组成多重集合，一共有 \(2^{n}-1\) 个真子集。对于一个包含 \(m\) 个数的子集 \(\{ a_{k_1},a_{k_2},\dots,a_{k_m} \}\)，蕴含的势能为 \(LCM(\frac{S}{a_{k_1}},\frac{S}{a_{k_2}},\dots,\frac{S}{a_{k_m}})\)，其中 \(LCM\) 表示最小公倍数。
请求出所有真子集的势能之和，因为答案很大，只需求出答案对 \(10^9+7\) 取模的结果。
\(1 \le n \le 10^6,1 \le a_i \le 10^6\)。
对于这种范围很小的而 \(n\) 很大的问题，我们考虑对值域下手。
LCM 是不好算的，但是很容易可以把它转化成 gcd 的问题，
于是这道题归根结底还是去求 gcd 恰好为 \(t\) 的个数。
可是这个东西这么算？
我们发现 gcd 是 \(t\) 的倍数是好算的，
于是想一想发现可以直接容斥，
\(f_t = (2^k-1) -f_{2t}-f_{3t}-\dots\)，其中 \(k\) 是为 \(t\) 的倍数的数的个数。
于是这样做一下就算完了，这道题也就做完了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=1e6+5;
int n,a[N],c[N],mx;
ll f[N],p[N],S,ans=0;
ll qpow(ll x,ll y){
ll res=1ll;
while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}
return res;
}
ll inv(ll x){return qpow(x,mod-2);}
void init(){
p[0]=1ll;
for(int i=1;i<=n;i++) p[i]=(p[i-1]+p[i-1])%mod;
}
int main(){
/*2023.12.20 H_W_Y #E. 石老板郁郁寡欢 LCM*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;S=1ll;init();
for(int i=1;i<=n;i++) cin>>a[i],c[a[i]]++,mx=max(mx,a[i]),S=1ll*S*a[i]%mod;
for(int i=mx;i>=1;i--){
int cnt=0;
for(int j=1;j*i<=mx;j++){
if(j!=1) f[i]=(f[i]-f[j*i]+mod)%mod;
cnt+=c[j*i];
}
f[i]=(f[i]+p[cnt]-1ll+mod)%mod;
ans=(ans+f[i]*S%mod*inv(i)%mod)%mod;
}
cout<<ans<<'\n';
}
F. 石老板阴阳调和 - 线性基
不会线性基寄了吧。
“你自由了！”锟斤拷星人对石老板说。
接着，石老板被飞船抛出，传送到了一个未知的星球上。当石老板回过神来时，发现自己被关入了一间黑暗的密室中。他用最后一根火柴点燃了火把，看到眼前有 \(n\) 个石柱，编号为 \(1,2,3,\dots,n\)。每个石柱上有不同的雕刻，有些石柱上的雕刻是凸出的，称之为“阳”；有些石柱上的雕刻是凹进去的，称之为“阴”。
石老板从壁画中了解到，可以通过点燃墙壁上的火炬改变石柱的阴阳状态。具体来说，一共有 \(m\) 个火炬，第 \(i\) 个火炬如果点燃，可以改变 \(k_i\) 个石柱的阴阳状态（阴变为阳，阳变为阴），这些石柱的编号为 \(z_{i,1},z_{i,2},\dots,z_{i,k_i}\)。只有把所有石柱都变为阴或者都变为阳，才能触发石门的机关，逃出密室。
现在有 \(q\) 种初始的情况，每种情况给出了初始 \(n\) 个石柱的阴阳状态，请你分别求出每种情况下有多少种方案能使得所有石柱都变为阴或者阳。两种方案不同当且仅当存在一个火炬在一种方案中点燃，另一种方案中未点燃，而与火炬点燃的顺序无关。
\(1 \le n,m,q \le 1500\)。
首先看到题目之后我们可以去列出一堆方程，
于是可以直接用高斯消元解方程，这样可以得到很大一部分分。
此时的答案其实就是方程中自由元的个数 \(cnt\) 的二的幂次方，也就是 \(2^{cnt}\)。
发现方程是异或的，于是直接用 bitset 维护一下，你可以得到原数据的满分。
这个时候我们就发现了，这道题其实就是线性基的板子，
我们用线性基维护一下就直接做完了，判断无解就是看当前给出的这种初始状态是不是可以被线性基表示出来即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=1500;
int n,m,q;
ll ans=1ll;
bitset<N> base[N];
bool ins(bitset<N> x){
for(int i=n-1;i>=0;i--)
if(x[i]){
if(base[i][i]) x=x^base[i];
else return base[i]=x,true;
}
return false;
}
int qry(bitset<N> x){
for(int i=n-1;i>=0;i--)
if(x[i]){
if(base[i][i]) x=x^base[i];
else return 0;
}
return 1;
}
int main(){
/*2023.12.20 H_W_Y #F. 石老板阴阳调和 线性基*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1,k;i<=m;i++){
cin>>k;bitset<N> b;
while(k--){
int x;cin>>x;
b[x-1]=1;
}
if(!ins(b)) ans=ans*2ll%mod;
}
while(q--){
bitset<N> b;
for(int i=0,x;i<n;i++) cin>>x,b[i]=x;
cout<<((qry(b)+qry(b.flip()))*ans%mod)<<'\n';
}
return 0;
}
G. 石老板告老还乡 - dp
石老板最喜欢的质数是 \(73939133\)，因为它的每个前缀都是质数。
在工作了 \(73939133\) 年后，石老板告老还乡，回到了他梦开始的地方。
寂寞的石老板买了一棵树，大小为 \(n\)，其中 \(1\) 号点是根节点。
老年生活应该是绚丽多彩的，所以他要对每个点进行染色。总共的颜色数有 \(m\) 种，所以他一共有 \(m^n\) 种颜色方案。
石老板这棵树的要求很高，所以染色必须满足 \(q\) 个要求，每个要求包含一个结点 \(p_i\) 和一个颜色 \(o_i\) ，表示从根到 \(p_i\) 的这条链上(含 \(p_i\) )所有节点里，必须包含 \(o_i\) 这种颜色。
现在石老板想知道满足要求的方案数是多少，当然这个答案可能很大，请输出它取模 \(73939133\) 后的值。
\(1 \le n \le 5000,m \le 10,q \le n \times m\)。
首先看到 \(m\) 这么小就感觉是状压，
确实也是这样，就是一个带状压的树形 dp，但状态设计可能有点技巧性。
我也来设计的状态是子树种的，这样的转移复杂度高达了 \(2^{2m}\)，很明显过不了。
于是这个时候我们考虑把状态转化到记录从 \(i\) 节点到根的颜色，
这样的复杂度就满足了，写起来就是类似于一个记忆化搜索。
具体来说，就是设 \(f_{i,j}\) 表示 \(i\) 到根的路径上的已有的颜色集合为 \(j\)，其子树中的方案数，
于是枚举一下这一个点是什么就做完了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll mod=73939133;
const int N=5005;
int n,m,q,head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
ll f[N][(1<<10)];
vector<int> g[N];
void add(int u,int v){
e[++tot]=(edge){v,head[u]};head[u]=tot;
e[++tot]=(edge){u,head[v]};head[v]=tot;
}
ll dfs(int u,int fa,int s){
if(f[u][s]!=-1) return f[u][s];
f[u][s]=0;
int t=-1;
for(auto i:g[u]){
if(!(s&(1<<i))){
if(t!=-1) return 0;
t=i;
}
}
for(int j=0;j<m;j++){
if(t!=-1&&j!=t) continue;
ll res=1ll;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
res=res*dfs(v,u,s|(1<<j))%mod;
}
f[u][s]=(f[u][s]+res)%mod;
}
return f[u][s];
}
int main(){
/*2023.12.20 H_W_Y #G. 石老板告老还乡 树形 dp*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
memset(f,-1,sizeof(f));
for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v);
for(int i=1,p,o;i<=q;i++) cin>>p>>o,g[p].pb(o-1);
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end()),g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
cout<<dfs(1,0,0)<<'\n';
return 0;
}
H. 石老板九五之尊 - 斜率优化
石老板的帝国日益强大，一共有 \(n\) 座城市，其中 \(1\) 号城市为首都，共有 \(n-1\) 条道路形成一个树形结构。
石老板王国科技不发达，如果某个城市发生了事情要报告给在首都的石老板，只能靠传信员人工送往首都。
每个城市都有传信员，从一个城市出发通往首都的路上遇到中间的城市，可以选择更换传信员，或者让原来的传信员继续传信。每个传信员传信速度都是一样的，但是会根据距离不同而改变，传信员走 \(L\) 距离需要 \(L^2\) 时间，如果中途更换传递员，则需要 \(P\) 时间来完成两个人的交接。
石老板想知道从任意一个城市出发给首都传信的最短时间的最大值是多少。
\(2 \le n \le 10^6\)。
猛然一看——贪心。
想多了，很明显是一个 dp，而且是一个树形 dp。
现在我们先来考虑序列上面的问题，设 \(f_i\) 表示前 \(i\) 个数的答案，
那么我们其实就是去找上一次交接的地方，于是有 dp 方程式（这里我们令 \(f_0=-P\) 这样可以避免算重。
其中 \(s\) 是前缀和。
于是稍微化简一下，你就发现这个东西可以直接斜率优化。
那放到树上，也就是加了一个类似于回滚莫队的撤销操作嘛，于是就做完了。
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define pb push_back
void prt(ll x){
int p[64],tmp=0;
if(x==0) putchar('0');
if(x<0) putchar('-'),x=-x;
while(x) p[++tmp]=x%10,x/=10;
for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
putchar('\n');
}
const int N=1e6+5;
int n,P,head[N],tot=0,l,r,q[N];
struct edge{int v,nxt,w;}e[N<<1];
ll f[N],s[N],ans=0;
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],w};head[v]=tot;
}
ll sq(ll x){return x*x;}
ll dx(int i,int j){return s[j]-s[i];}
ll g(int i){return f[i]+sq(s[i]);}
ll dy(int i,int j){return g(j)-g(i);}
void dfs(int u,int fa){
int _l=l;
vector<int> g;g.clear();
while(l<r&&dy(q[l],q[l+1])<=(ll)2*s[u]*dx(q[l],q[l+1])) ++l;
f[u]=f[q[l]]+sq(s[u]-s[q[l]])+(ll)P;
while(l<r&&dx(q[r],u)*dy(q[r-1],q[r])>=dx(q[r-1],q[r])*dy(q[r],u)) g.pb(q[r]),--r;
q[++r]=u;
ans=max(ans,f[u]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
s[v]=s[u]+(ll)e[i].w;
dfs(v,u);
}
--r;
for(int i=g.size()-1;i>=0;i--) q[++r]=g[i];
l=_l;
}
int main(){
/*2023.12.20 H_W_Y #H. 石老板九五之尊 斜率优化*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>P;
f[0]=(ll)-P;l=r=1;q[1]=0;
for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,add(u,v,w);
dfs(1,0);prt(ans);
return 0;
}
Conclusion
- c++ 20 之后就不能用
char s;cin>>s+1;了。（A. [NOIP2022] 种花） - 树形 dp 的状态不只是可以维护子树中的状态，还可以记录 \(i\) 到根节点的状态。（G. 石老板告老还乡）
- 算 gcd 恰好为 \(t\) 的个数时，我们考虑先算出是 \(t\) 的倍数的个数，在去减去 \(f_{2t},f_{3t},\dots\)。（E. 石老板郁郁寡欢）
- 有关 LCM 的问题我们可以很平凡的转化成 gcd 的问题，当然是大多数情况。（E. 石老板郁郁寡欢）