排列
题目描述
求有多少个长度为 \(n\) 且任意相邻两个数的最大公约数都不为 \(k\) 的排列？
数据范围
满足 \(1≤n≤3000,1≤\frac{n}{k}≤10\)。
题解
这个数据范围很有深意，产生影响的数字至多有 \(10\) 个。
赛时想的是 容斥原理+爆搜得出答案（没有正确性）。
正解是 状压\(dp\)，
设 \(dp_{i,j,k}\)，表示第 \(i\) 位选过的数字集为 \(j\)，最后一位为 \(k\)。
不产生影响的数字可看成一类。
易得 \(dp\) 柿子。
代码
#include<iostream>
#include<vector>
#define int long long
using namespace std;
int gcd(int a,int b){ return (!b)?a:gcd(b,a%b); }
constexpr int M=1030,p=998244353;
int n,K,Maxn,ans,dp[2][M][15];
vector<int> v;
signed main(){freopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>K;for(int i=1;i<=n/K;i++)v.push_back(K*i);for(int i=0;i<v.size();i++)dp[0][1<<i][i]=1;dp[0][0][v.size()]=1,Maxn=(1<<v.size())-1;for(int i=2;i<=n;i++){for(int j=0;j<=Maxn;j++){for(int k=0;k<v.size();k++){//末尾是含 k 的数 if(!((j>>k)&1))continue;int x=(j^(1<<k));dp[1][j][k]=dp[0][x][v.size()];//不含 k for(int l=0;l<v.size();l++){//含 k 且公约数不为 k if(!((x>>l)&1))continue;if(gcd(v[k],v[l])==K)continue;dp[1][j][k]+=dp[0][x][l],dp[1][j][k]%=p;}}for(int k=0;k<=v.size();k++)//末尾不是含 k 的数 dp[1][j][v.size()]+=dp[0][j][k],dp[1][j][v.size()]%=p;}for(int j=0;j<=Maxn;j++)for(int k=0;k<=v.size();k++)dp[0][j][k]=dp[1][j][k],dp[1][j][k]=0;}for(int i=0;i<=v.size();i++)ans+=dp[0][Maxn][i],ans%=p;for(int i=n-v.size();i;i--)ans=ans*i%p;cout<<ans<<'\n';return 0;
}
战场模拟器
题目描述
战场模拟器中，\(N\) 个英雄正在与魔王战斗。
这 \(N\) 个英雄排成一排，其中位置 \(i(1≤i≤N)\) 的英雄最初的生命值为 \(A_i\)。
在每个时刻，每个英雄都有以下其中一种状态：
1.生命值 < 0 的英雄被视为死亡，而已经死亡的英雄则会永远死亡。
2.生命值 = 0 的英雄被视为濒死。他们还未死亡，但处于危险之中。
3.生命值 > 0 的英雄被视为健康。
总共有 \(Q\) 个事件，依时间顺序发生：
1 L R x： 魔王攻击从位置 \(L\) 到位置 \(R\)（含）的英雄。对于每个英雄 \(i(L≤i≤R)\)，英雄 \(i\) 的生命值会减少 \(x\)。
2 L R x： 法师治疗从位置 \(L\) 到位置 \(R\)（含）的英雄。对于每个英雄 \(i(L≤i≤R)\)，如果英雄 \(i\) 还没有死亡，那么英雄 \(i\) 的生命值会增加 \(x\)。
3 h： 为英雄 \(h\) 提供护盾，防止下次攻击对 \(h\) 造成伤害。一个英雄可以拥有多个护盾，而每次受到攻击都会消耗一个护盾。
4 L R： 查询从位置 \(L\) 到位置 \(R\)（含）之间死亡的英雄数量。
5 L R： 查询从位置 \(L\) 到位置 \(R\)（含）之间濒死的英雄数量。
输入格式
第一行输入包含一个整数 \(N\)。
第二行输入包含 \(N\) 个整数 \(A_1,A_2,…,A_N\)。
第三行输入包含一个整数 \(Q\)。
接下来的 \(Q\) 行依时间顺序分别描述一个事件。
输出格式
对于每个类型 \(4\) 或类型 \(5\) 事件，输出一行一个数字，代表该查询的答案。
数据范围+子任务
对于所有测试数据，\(1≤N,Q≤2×10^5\)
1.\(L_j=R_j\)
2.只有类型 \(1\)、类型 \(2\) 或类型 \(5\) 的事件，可以保证没有英雄死亡
3.只有类型 \(1\)、类型 \(2\)、类型 \(3\) 或类型 \(5\) 的事件，可以保证没有英雄死亡
4.只有类型 \(1\)、类型 \(4\) 或类型 \(5\) 的事件
5.无附加限制
题解
分成以下几个子任务：
子任务2
显然可以用普通线段树，维护 区间最小值 和 最小值个数。
子任务3
在 子任务2 基础上增加了“护盾”操作。
注意到至多有 \(Q\) 个护盾操作，而每次攻击操作会消耗护盾操作。
考虑暴力，将护盾操作存储下来，攻击操作分开处理。
时间复杂度为 \(O((N+Q)logN)\)
子任务4
考虑势能线段树。
发现一个人至多死一次。
因此发现 \(minn<0\) 就暴力更新子树。
时间复杂度为 \(O((N+Q)logN)\)
子任务5
综合上述做法。
代码
#include<iostream>
#include<map>
#define lch (x<<1)
#define rch (x<<1|1)
#define int long long
using namespace std;
constexpr int N=2e5+5;
int n,m,a[N];
struct State{ int minn,cnt1,cnt2; };
struct Segment_Tree{State d[N<<2];int tag[N<<2];State merge(State x,State y){State ans=State{1,x.cnt1+y.cnt1,x.cnt2+y.cnt2};if(x.minn<0)ans.minn=y.minn;else if(y.minn<0)ans.minn=x.minn;else if(x.minn<y.minn)ans.minn=x.minn,ans.cnt2=x.cnt2;else if(y.minn<x.minn)ans.minn=y.minn,ans.cnt2=y.cnt2;else ans.minn=x.minn;return ans;}void build(int x,int L,int R){if(L==R){ d[x]=State{a[L],0,1}; return; }int mid=(L+R)>>1;build(lch,L,mid),build(rch,mid+1,R);d[x]=merge(d[lch],d[rch]);}void update(int x,int L,int R){if(d[x].minn>=0||d[x].cnt1==(R-L+1))return;if(L==R){d[x].cnt1=1,d[x].cnt2=0; return;}int mid=(L+R)>>1;tag[lch]+=tag[x],d[lch].minn+=tag[x];tag[rch]+=tag[x],d[rch].minn+=tag[x];tag[x]=0;update(lch,L,mid),update(rch,mid+1,R);d[x]=merge(d[lch],d[rch]);}void push_down(int x,int L,int R){tag[lch]+=tag[x],d[lch].minn+=tag[x];tag[rch]+=tag[x],d[rch].minn+=tag[x];int mid=(L+R)>>1; tag[x]=0;update(lch,L,mid),update(rch,mid+1,R);}void add(int x,int l,int r,int val,int L,int R){if(l>r)return;if(l==L&&r==R){d[x].minn+=val; tag[x]+=val;update(x,L,R); return;}int mid=(L+R)>>1; push_down(x,L,R);if(r<=mid)add(lch,l,r,val,L,mid);else if(mid+1<=l)add(rch,l,r,val,mid+1,R);else add(lch,l,mid,val,L,mid),add(rch,mid+1,r,val,mid+1,R);d[x]=merge(d[lch],d[rch]);}State query(int x,int l,int r,int L,int R){if(l==L&&r==R)return d[x];int mid=(L+R)>>1; push_down(x,L,R);if(r<=mid)return query(lch,l,r,L,mid);else if(mid+1<=l)return query(rch,l,r,mid+1,R);else return merge(query(lch,l,mid,L,mid),query(rch,mid+1,r,mid+1,R));}
}tr;
map<int,int> mp;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];tr.build(1,1,n);cin>>m;for(int i=1,opt,L,R,x;i<=m;i++){cin>>opt;if(opt==1){cin>>L>>R>>x;if(!mp.empty()){map<int,int>::iterator it=mp.lower_bound(L);while(!mp.empty()&&it!=mp.end()&&(*it).first<=R){tr.add(1,L,(*it).first-1,-x,1,n);(*it).second--,L=(*it).first+1; if((*it).second==0)mp.erase(it);if(!mp.empty())it=mp.lower_bound(L);}}tr.add(1,L,R,-x,1,n);}else if(opt==2){cin>>L>>R>>x;tr.add(1,L,R,x,1,n);}else if(opt==3){cin>>x; if(!tr.query(1,x,x,1,n).cnt1)mp[x]++;}else if(opt==4){cin>>L>>R;State ans=tr.query(1,L,R,1,n);cout<<ans.cnt1<<'\n';}else {cin>>L>>R;State ans=tr.query(1,L,R,1,n);cout<<ans.cnt2*(!ans.minn)<<'\n';}}return 0;
}
点亮
太困难了，参见 P12992