CF1266G

神仙结论题。

题意：把 $1$ 到 $n$ 的排列按照字典序排列在一起，序列长度为 $n*n!$ ，求该序列中本质不同的子串个数，对 $998244353$ 取模， $n \leq 10^6$ 。

首先设 $f(i)= \max_{j=0}^{i-1} lcp(i,j),lcp(i,j)$ 表示原序列中以 $i,j$ 为首的后缀的最长公共前缀。

则答案为 $\frac{S(S+1)}{2}- \sum_{i=0}^{S-1}f(i),S=n \times n!$ 。就是所有子串减去重复的，重复的子串只算最早出现的一次。

结论1：对于所有 $i \neq j,lcp(i,j)<2n$ 。

假设有两个后缀最长公共前缀长度不小于 $2n$ ，则一定会出现如下图所示情况：

$[a,b]$ 代表的子串与 $[c,d]$ 代表的子串相等（其中|_|代表一个排列）。

|                a||                b|

          |      c          ||      d          |

于是 $a=c,b=d$ ，又因为 $a \neq b$ ，所以 $c \neq d$ ，从而 $c$ 到排列末尾的数单调递减。

同理，排列开头到 $c$ 的数单调递减，所以， $c$ 所在整个排列中的数单调递减（这意味着该排列应该处在整个序列的末尾）。

又因为该排列后面还有至少一个排列，所以 $lcp(i,j) \geq 2n$ 不可能成立。

结论2：设 $cnt(a,i)$ 表示 $n=a$ 时满足 $f(j)=i$ 的 $j$ 的个数，则对于 $0 \leq i

结论3： $cnt(n,1)=n^2-2n+2$ 。

对于序列中连续两个数，两者相同的情况只会出现一次（以 $1$ 开头的最后一个排列最后一位数开始是 $2,2,1,3,4...$ ）。

所以连续两个数的组成一共有 $n^2-n+1$ 中情况。除去 $f=0$ 的情况，再加上整个序列的最后一项，可得 $cnt(n,1)=n^2-2n+2$ 。

结论4：对于 $n>1,1

证明以上结论后题目就没有难度了。

#include
#include
#include
using namespace std;
#define ll long long int
#define mod 998244353
inline int mul(int a,int b){return (int)((ll)a*b%mod);}
inline int pow(int a,int b)
{
 int res=1;
 while(b>0){
  if(b&1)
   res=mul(res,a);
  a=mul(a,a);
  b>>=1;
 }
 return res;
}
inline int inv(int x){return pow(x,mod-2);}
int n,ans=0,facn=1,fac,t;
inline int F(int x){return mul(x-1,x-1)+1;}
int main(void)
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  facn=mul(i,facn);
 ans=mul(mul(facn,n),mul(mul(facn,n)+1,inv(2)));
 fac=facn;
 for(int i=1;i){
  if(i>1) fac=mul(fac,inv(n-i+2));
  t=mul(mul(facn,inv(fac)),F(n-i+1));
  ans=(ans-mul(i,t)+mod)%mod;
  t=(facn-t+mod)%mod;
  ans=(ans-mul(n+i,t)+mod)%mod;
 }
 t=facn-n+mod;
 ans=(ans-mul(t,n)+mod)%mod;
 printf("%d\n",ans);
 return 0;
}
/*
*/