提高组数学专题 1
T1 [CF1909F1] Small Permutation Problem (Easy Version)
将排列的每项 \(p_i\) 记成 \((i,p_i)\) 的形式，则问题转化为：在一个 \(n\times n\) 的棋盘上放置 \(n\) 个車，使这些車互不攻击，且满足题目中 \(a\) 的限制。
题目中 \(a_i\) 的限制实际上就是限制了左上角的 \(i\times i\) 棋盘中車的数量，考虑与 \(a_{i-1}\) 作差，则进一步转化为包含 \((i,i)\) 的一个 “L 形” 区域的車的数量。结合每行每列都只有一个車，则 \(a_i-a_{i-1}\) 的取值只可能有 \(0,1,2\) 三种情况，否则必无解。
设一个 \(k\) 表示当前空下来的能放車的行列数，对于 \(\mathit{ans}\) 的计算有三种情况：
- \(a_i-a_{i-1}=0\)，说明这一行列空下了，\(k\gets k+1\)；
- \(a_i-a_{i-1}=1\)，说明要么在空下的 \(k\) 行或 \(k\) 列放，要么在 \((i,i)\) 放，\(\mathit{ans}\gets\mathit{ans}\times(2k+1)\)，\(k\) 不变；
- \(a_i-a_{i-1}=2\)，说明必须在空下的 \(k\) 行和 \(k\) 列各放一个，则 \(\mathit{ans}\gets\mathit{ans}\times k^2\)，然后 \(k\gets k-1\)。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0) putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top) putchar(str[--top]+48);
if(sf^'#') putchar(sf);
}
constexpr int MAXN=2e5+5,MOD=998244353;
int T,n,a[MAXN];
bool fool(){
for(int i=1;i<=n;++i) if(a[i]>i||a[i]-a[i-1]>2) return 1;
return 0;
}
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
if(a[n]^n||fool()){
write(0);
continue;
}
long long ans=1,k=0;
for(int i=1;i<=n;++i)
switch(a[i]-a[i-1]){
case 0: ++k; break;
case 1: ans=ans*(k<<1|1)%MOD; break;
default:ans=ans*k%MOD*k%MOD;--k; break;
}
write(ans);
}
return fw,0;
}
T2 [CF1909E] Multiple Lamps
这题的 \(\lfloor n/5\rfloor\) 非常 bug，我们一时想不出对应的维护方法。
但仔细一想就可以发现，这个类似素数筛一样的开灯规则使得如果挨个开灯，最后亮着的一定是完全平方数。而 \(n\) 以内的完全平方数数量在 \(n\ge20\) 时永远是 \(\le\lfloor n/5\rfloor\) 的，所以对于 \(n\ge20\) 直接挨个输出 \(1\sim n\) 即可。同理，显然如果 \(n\le4\) 则无解。
于是此题原本 \(n\le2\times10^5\) 的范围一下子缩小到了 \(5\le n\le19\)。
数据范围小了许多，我们可以暴力枚举状态。具体地，预处理 \(n\in[5,19]\) 时所有满足条件的开灯顺序。对于每组 \(m\)，检查所有的可能答案中是否有满足 \(m\) 条限制的答案，如果有直接输出。
预处理复杂度是 \(O(n2^nn\log\log n)=O(2^nn^2\log\log n)\)，检查复杂度是 \(O(\text{siz}(\mathit{ans}_n)\times m)\) 的。将 \(n=19\) 代入发现不到 \(2\times10^8\)，可以通过本题。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0) putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top) putchar(str[--top]+48);
if(sf^'#') putchar(sf);
}
constexpr int MAXN=2e5+5;
int T,n,m;
struct{
int x,y;
}a[MAXN];
vector<int>ans[20];
int main(){
for(int i=5,B;i<=19;++i){
B=1<<i;
for(int s=1,sta;s<B;++s){
sta=0;
for(int j=1;j<=i;++j){
if(!(s&(1<<(j-1)))) continue;
for(int k=j;k<=i;k+=j) sta^=1<<(k-1);
}
if(__builtin_popcount(sta)*5<=i) ans[i].emplace_back(s);
}
}
T=read();
while(T--){
n=read(),m=read();
for(int i=1;i<=m;++i) a[i]={read()-1,read()-1};
if(n<5){
write(-1);
continue;
}else if(n>19){
write(n);
for(int i=1;i<=n;++i) write(i,' ');
putchar('\n');
continue;
}
for(auto s:ans[n]){
for(int i=1;i<=m;++i) if(s&1<<a[i].x&&!(s&1<<a[i].y)) goto sht;
write(__builtin_popcount(s));
for(int j=0;j<n;++j) if(s&1<<j) write(j+1,' ');
putchar('\n');
goto byby;
sht:;
}
write(-1);
byby:;
}
return fw,0;
}