【洛谷比赛】你的名字 T2日常

题面

泷打工的餐厅正在举行摆盘大赛，你能帮助泷拿到尽量高的奖金吗？泷拿到奖金后会请三叶和你喝咖啡的！

餐厅提供了n个盘子，分别编号为n1,2,⋯,n。把它们排成一行，排好后第(1≤i≤n)个盘子的编号为a_{i}ai​，此时称序列a1​,a2​,⋯,an​为一种摆法，也就是说每一种摆法恰为1~n的一个排列。如3个盘子的不同摆法有1,2,3，1,3,2，2,1,3，2,3,1，3,1,2，3,2,1六种。

两种摆法比较大小的方法如下：首先比较第1个盘子的序号；如果第1个盘子的序号相同，则再比较第2个盘子的序号；如果第2个盘子的序号也相同，再比较第3个盘子的序号……依此类推。我们称这种比较摆法大小的方法为按字典序比较。上面列举的3个盘子的所有摆法就是按照字典序从小到大给出的。

餐厅主管喜欢不同寻常的摆法。他定义摆法a的“错乱数”为摆法aa中满足ai​≠i的ii的数量，如摆法1,2,3的错乱数为0，摆法1,3,2的错乱数为2，摆法3,2,1的错乱数也为2。根据自己的喜好，餐厅主管对每一个错乱数k(0≤k≤n)设置了基础奖金ck​。

摆盘大赛的规则如下：选手选定某一个错乱数k，按字典序从小到大摆出所有错乱数为k的摆法，如果他摆出的摆法共有d种，那么他得到的奖金为dm=ck​×d。当然，餐厅主管的钱有限，最终发放的奖金为m mod 993244853的值。

现在泷想拿到最高的奖金。请你帮他找出k，使得他最终得到的奖金最多，并告诉他奖金的最大值和错乱数为k的字典序最小的摆法。如果有k1​<k2​，且错乱数为k1​与错乱数为k2​时最终得到的奖金都为最大值，则输出错乱数为k1​时的摆法。

输入格式：

输入共2行。
第1行有1个正整数n，表示餐厅提供的盘子的数目。
第2行有n+1个非负整数，第k(0≤k≤n)个整数ck​表示所选错乱数为k时的基础奖金。

输出格式：

设选定错乱数为k时，最终得到的奖金最大。k不必输出。
输出共2行。
第1行有1个非负整数，表示最终得到的奖金的最大值。
第2行有n个正整数，表示错乱数为k，且字典序最小的摆法。

分析

我觉得是很困难的数学题了！

自己做的时候只能推出来一个全错排的递推式 

 an=A(n,n)-a2*C(n,2)-a3*C(n,3)-……-an-1*C(n,n-1)-1

没错，又是组合数，又是排列数，我当时打表找规律找到眼睛痛才推出来这个，然而是真的化不来简了！！放弃T T

这题太毒了，首先你得了解一下这个

然后你能愉快地得到一个公式

看了这个公式你会发现，你需要递推求逆元。

然后借用出题人的图

你会发现保证字典序最小有个奇特的规律

前面k项都是左右相邻项交换，最后两项才有变，第k−1个是k，当k是奇数时第k个是k-2，当k是偶数时第k个是k-1。

而且根据红色字体也可看出规律吧。

按照字典序的定义，我们只要优先保证在前面的位置上放置最小的元素，就能保证字典序最小。
若k是偶数，那么前k−2个元素是完整的两两邻项交换（参见上图），最后两个元素也如法炮制进行邻项交换即可。
若k是奇数，那么k−2也是奇数，按上面的邻项交换法则，第k−2个元素是k−1。这样，前k−2个元素的邻项交换便是不完整的。此时如果第k−1个位置仍按邻项交换的方法放置k−2，第k个元素就只能是k，不满足完全错排的条件。因此，第k−1个位置只能放k，而要在第k个位置上放k−2。
就这样，我们找出了生成字典序最小的完全错排的方法。结合前面的讨论，我们就可以生成答案了。

代码

#include <cstdio>
#include <cctype>
#define MAXN 1000005
#define MOD 993244853
#define MAXL 25
using namespace std;
typedef long long ll;
int cost[MAXN],tmp[MAXL],inv[MAXN],b[MAXN],c[MAXN],ansb[MAXN];
ll read()
{
    ll ans=0;
    char ch;
    do {
        ch=getchar();
    } while (!isdigit(ch));
    while (isdigit(ch)){
        ans=ans*10+(ch-'0');
        ch=getchar();
    }
    return ans%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){
  
    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; 
    ansb[n+pos-1]=n+((n&1)?(-2):(-1))+k;
}

int main() 
{
    int n;
    int maxans,maxi=0;
       n=read();
    for (int i=0;i<=n;i++)
        cost[i]=read();
    inv[1]=1;
    for (int i=2;i<=n;i++)
        inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
    c[0]=b[0]=1;
    c[1]=n%MOD,b[1]=0;
    maxi=0,maxans=cost[0];
    for (int i=2;i<=n;i++)
    {
        ll t; 
        c[i]=ll(c[i-1])*(n-i+1)%MOD;
        c[i]=ll(c[i])*inv[i]%MOD;
        b[i]=ll(i-1)*(b[i-1]+b[i-2])%MOD;
        t=ll(b[i])*c[i]%MOD;
        t=t*cost[i]%MOD;
        if (t>maxans)
        {
            maxans=t;
            maxi=i;
        }
    }
    write(maxans);
    putchar('
');
    for (int i=1;i<=n-maxi;i++)
        ansb[i]=i;
    if (maxi) 
        make_b(n-maxi+1,maxi,n-maxi);
    for (int i=1;i<=n;i++)
    {
        write(ansb[i]);
        putchar(' ');
    }
    putchar('
');
    return 0;
}