Codeforces 1091D New Year and the Permutation Concatenation
题目链接
http://codeforces.com/contest/1091/problem/D
题目大意
将 $1$ 到 $n$ 的所有全排列按照字典序排序拼接在一起，问有多少个长度为 $n$ 的连续子串中所有数的和为 $\frac{n(n + 1)}{2}$，结果对 $998244353$ 取模。
题目分析
由题意可以将所求的子串分成两种情况，第一种是单独的一个排列，第二种是横跨两个排列的子串。
第一种情况的答案很显然，每一种排列都是满足题意的，共有 $n!$ 种。
对于第二种情况，考虑使用 $n – 1$ 的答案去构造 $n$ 的答案。显然可知，对于两个相邻的排列，假如第一位的数不一样，那么肯定是不满足题目要求的，也就是说只有开头为相同数字的两个排列之间才会有满足题意的子串。那么很显然以 $n$ 个数各自开头的所有排列所满足题意的子串数量应该是相同的。
那么现在可以以开头为 $n$ 的排列为例。开头为 $n$ 的排列相当于在 $n – 1$ 的串中每个排列前面加一个 $n$ 。很明显原本在 $n – 1$ 时横跨两个排列满足题意的子串在加入一个 $n$ 后仍满足题意。而所有的不横跨两个排列的情况，每个和他们后面的一个 $n$ 结合便可以构造出新的横跨两个排列的子串。但是要注意到最后一个排列后面没有 $n$ 供它结合。这样就可以构造出所有的新的子串。
如此一来，加入 $n – 1$ 的答案为 $f(n – 1)$ 的话，那么答案便为 $f(n) = (f(n – 1) – 1)n + n!$，线性求解即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
long long n, m, t;
long long mod = 998244353;
int main(){
long long i, j;
long long ans = 1;
long long fac = 1;
cin >> n;
for(i=2;i<=n;i++){
fac = fac * i % mod;
ans = ((((ans - 1 + mod) % mod) * i % mod) + fac) % mod;
}
cout << ans << endl;
return 0;
}