你的名字。信息学奥林匹克 日常 题解

### 你的名字。信息学奥林匹克 日常 题解 #### 小提示 请注意这题的模数是$993244853$而非$998244353$！ 事实上，$998244353, 993244853, 998244853$都是质数，而$993244353=3\times 331081451$。 ~~（打死毒瘤出题人）~~ 出题人因为使用了奇怪的模数，浪费了大家的时间，在此诚挚道歉。 #### 致谢 感谢[皎月半洒花](https://www.luogu.org/space/show?uid=28313)大佬发现了本题题面的错误。 #### $5$分~~算法~~ 观察数据范围，“对于5%的数据，满足除$c_{0}\neq 0$外，所有$c_{k}=0(k>0)$”，即有5%的数据是以$1,2,\cdots ,n$作为答案的。由于错乱数为$0$的摆法只有$1$种，第一行只需输出$c_{0}$，第二行输出$1,2,\cdots ,n$即可。 ```cpp #include <iostream> #define MOD 993244853 using namespace std; int main(void){ int n; int c0; cin >> n >> c0; cout << c0%MOD << endl; for (int i=1;i<=n;i++) cout << i << ' '; return 0; } ``` #### $20$分暴力做法 首先用上面的方法拿到$5$分。对于其他不满足特殊条件的数据，使用[$\text{next\_permutation}$](https://zh.cppreference.com/w/cpp/algorithm/next_permutation)枚举所有摆法，统计每一个错乱数对应的摆法数$d$。通过计算确定答案的错乱数后，再使用一次$\text{next\_permutation}$找到字典序最小的摆法。 时间复杂度$\text{O}(n!)$，可以通过$n\le 11$的数据。（实现得好也许可以通过$n \le 12$？） ```cpp #include <iostream> #include <algorithm> //next_permutation #define MAXN 105 //n大于100的数据一定是无法通过的～ #define MOD 993244853 using namespace std; int tarr[MAXN]; //保存当前枚举到的摆法 int c[MAXN]={0},d[MAXN]; //变量含义同题目 int calc(int n); //计算错乱数 int main(void){ int n; int ok=1; //ok=1表示那5%数据的特殊情况 int mans=0,mi=0; //mans - max ans，mi是答案对应的错乱数 cin >> n; for (int i=0;i<=n;i++){ int ti; cin >> ti; //ti即c[i] if (!i){ //如果i=0，直接赋值 c[0]=ti; continue; } //i>0 if (!ti) //以下语句可删除（和1做或运算没有必要） ok|=1; //注意c数组已被初始化为全0，无需赋值 else //存在c[k]>0，不满足特殊条件 ok=0,c[i]=ti; } if (ok){ //满足特殊条件，直接拿分 cout << c[0]%MOD << endl; for (int i=1;i<=n;i++) cout << i << ' '; cout << endl; return 0; } //不满足特殊条件，暴力枚举 for (int i=1;i<=n;i++) tarr[i]=i; //初始化 //统计每个错乱数对应的摆法数d do { int ti=calc(n); d[ti]++; if (d[ti]==MOD) d[ti]=0; //相当于d[ti]%=MOD } while (next_permutation(tarr+1,tarr+n+1)); //统计奖金最高的错乱数 for (int i=0;i<=n;i++) if (c[i]*(long long)(d[i])%MOD>mans) mans=c[i]*(long long)(d[i])%MOD,mi=i; cout << mans << endl; //找到错乱数为mi的字典序最小的排列 for (int i=1;i<=n;i++) tarr[i]=i; while (calc(n)!=mi) next_permutation(tarr+1,tarr+n+1); for (int i=1;i<=n;i++) cout << tarr[i] << ' '; cout << endl; return 0; } int calc(int n){ //计算错乱数 int ans=0; for (int i=1;i<=n;i++) if (tarr[i]!=i) ans++; return ans; } ``` #### $100$分数学做法 **警告：以下内容十分乏味，如果感到不适，请立即停止阅读。** 满分做法需要进行一些分析。 我们容易知道，错乱数为$1$的摆法是不存在的。 为了方便叙述，我们把有$k$个元素且错乱数为$k$的摆法称为$k$个元素的完全错排，即每个元素都不在自己位置上的排列。 $k$个元素的完全错排数量在下文中记为$b_{k}$。$b_{k}$有自己的递推公式，$b_{0}=1, b_{1}=0, b_{i}=(i-1)\times (b_{i-1}+b_{i-2})$。 这里介绍一下讲解完全错排的一篇文章：[洛谷日报 #52 [Planet6174]小学生都能看懂的错排问题解析](https://www.luogu.org/blog/P6174/post-cuo-pai)。为节省篇幅（~~其实是为了偷懒~~） ，此处不再讲解$b_{k}$递推公式的原理。 下文的叙述中需要用到组合数$C^{n}_{k}$。组合数也有递推公式$C^{n}_{i}=C^{n}_{i-1}\times (n-i+1)\div i$。 为了在$\mod 993244853$的意义下进行除法，我们还必须递推出$1$～$n$的数的逆元，递推公式为$i^{-1}=(p-\lfloor p/i \rfloor)\times (p\mod i)^{-1} \mod p$，此处也不再讲解，请移步[P3811 【模板】乘法逆元 题解](https://www.luogu.org/problemnew/solution/P3811)。 首先，我们需要看到“错乱数为$k$”的摆法的本质，就是从所有$n$个元素中选出$k$个进行完全错排，剩余$n-k$个元素保持原样（不构成错乱）。因此错乱数为$k$的摆法数即为$C^{n}_{k}\times b_{k}$。 接着，我们发现，字典序最小的错乱数为$k$的摆法，一定是前$n-k$个元素保持原样，后$k$个元素构成完全错排（用字典序的定义比较容易证明）。而在从$1$到$k$的完全错排中，每个元素加上$n-k$，就可以得到从$n-k+1$到$n$的完全错排。 因此，问题就转化为求字典序最小的完全错排。 经过暴力求解，我们有了发现。  上图列出了$k=2$到$k=15$的字典序最小的完全错排，斜着看更能发现规律。 可以看到，$k$个元素的上述错排中，前$k-2$个都是邻项交换（即第$2m$个是$2m-1$，第$2m-1$个是$2m$，其中$m\le 1$）。 而最后两个元素比较特殊，第$k-1$个是$k$，当$k$是奇数时第$k$个是$k-2$，当$k$是偶数时第$k$个是$k-1$。 这个规律是可以证明的。 按照字典序的定义，我们只要优先保证在前面的位置上放置最小的元素，就能保证字典序最小。 首先考虑前$k-2$个元素。第$1$个位置上能放的最小元素是$2$，在此情况下，第$2$个位置上能放的最小元素是$1$。以此类推，第$2m-1$个位置上能放的最小元素就是$2m$，第$2m$个位置上能放的最小元素就是$2m-1$。 对于最后两个位置，我们按$k$的奇偶性分别讨论。 若$k$是偶数，那么前$k-2$个元素是完整的两两邻项交换（参见上图），最后两个元素也如法炮制进行邻项交换即可。 若$k$是奇数，那么$k-2$也是奇数，按上面的邻项交换法则，第$k-2$个元素是$k-1$。这样，前$k-2$个元素的邻项交换便是不完整的。此时如果第$k-1$个位置仍按邻项交换的方法放置$k-2$，第$k$个元素就只能是$k$，不满足完全错排的条件。因此，第$k-1$个位置只能放$k$，而要在第$k$个位置上放$k-2$。 就这样，我们找出了生成字典序最小的完全错排的方法。结合前面的讨论，我们就可以生成答案了。 时间复杂度为$\text{O}(n)$，完全可以通过所有的数据。输入输出量比较大，建议写读入输出优化。（其实$\text{cin,cout}$也可以过的。） ```cpp #include <cstdio> #include <cctype> #define MAXN 1000005 #define MOD 993244853 #define MAXL 25 using namespace std; typedef long long ll; int cost[MAXN]; //即题中的c，基础奖金 int tmp[MAXL]; //输出优化的缓存 int inv[MAXN];//乘法逆元 int b[MAXN];//完全错排数 int c[MAXN];//nCi，组合数 int ansb[MAXN];//所求排列 ll read(void); //读入优化 void write(int x); //输出优化 void make_b(int pos,int n,int k); //生成所求字典序最小的摆法 int main(void) { int n; int maxans,maxi=0; n=read(); for (int i=0;i<=n;i++) cost[i]=read(); //线性递推求逆元 inv[1]=1; //1的逆元是本身 for (int i=2;i<=n;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD; //nC0=1，定义0个元素的完全错排数为1(b[0]=1) c[0]=b[0]=1; //nC1=n，1个元素的完全错排数为0 c[1]=n%MOD,b[1]=0; //初始化最大奖金的错乱数为0 maxi=0,maxans=cost[0]; //错乱数是不可能为1的，这辈子不可能为1的 for (int i=2;i<=n;i++){ ll t; //t表示错乱数为i时的奖金 //递推组合数 c[i]=ll(c[i-1])*(n-i+1)%MOD; c[i]=ll(c[i])*inv[i]%MOD; //nCi=nC(i-1)*(n-i+1)/i //递推完全错排数 b[i]=ll(i-1)*(b[i-1]+b[i-2])%MOD; //错乱数为i的摆法数即为b[i]*c[i] t=ll(b[i])*c[i]%MOD; //计算奖金 t=t*cost[i]%MOD; if (t>maxans){ maxans=t; maxi=i; } } write(maxans); putchar('\n'); for (int i=1;i<=n-maxi;i++) ansb[i]=i;//对前n-max_i个盘子，编号为本身 if (maxi) //如果答案错乱数不为0，就要使用make_b生成答案摆法 //从n-maxi+1（第一个错乱的盘子）开始，生成maxi个错乱的盘子 make_b(n-maxi+1,maxi,n-maxi); for (int i=1;i<=n;i++){ //输出答案 write(ansb[i]); putchar(' '); } putchar('\n'); return 0; } ll read(void){ ll ans=0; char ch; do { ch=getchar(); } while (!isdigit(ch)); while (isdigit(ch)){ ans=ans*10+(ch-'0'); ch=getchar(); } return ans%MOD; //所有输入的数据都可以直接%MOD } void write(int x){ int lg=0; if (!x){ putchar('0'); return; } while (x){ tmp[lg++]=x%10; x/=10; } for (int i=lg-1;i>=0;i--) putchar(tmp[i]+'0'); } void make_b(int pos,int n,int k){ //这个函数生成字典序最小的摆法 //生成的实质是：生成1~n的字典序最小的完全错排，再把每个元素+k for (int i=pos,j=1;i<n+pos-2;i++,j++) //前面的元素都是两两交换 ansb[i]=j+((j&1)?1:-1)+k; //最后两个元素比较特殊 ansb[n+pos-2]=n+k; //倒数第二个元素是n ansb[n+pos-1]=n+((n&1)?(-2):(-1))+k; //最后一个元素，当n是奇数时是n-2，当n是偶数时是n-1 } ```