这是goodbye2018的D题，红包赛第一场的C题
是我打的第一场CF
不知道为什么每次一补到这一场我就要强调一遍这是我的第一场CF......
....
....
真矫情
不过还挺有仪式感的，嗯嗯~ o(￣▽￣)o
看题吧
这题是肯定有公式的，不然这么乱七八糟的真的很难找规律，而且题目的名字就是permutation concatenation
这个题目真的很坏，只给了n=3时ans=9；n=4时ans=56；
其实如果知道了n=5时，ans=395，问题就迎刃而解了

我的方法跟官方题解的不一样，题解用的是分析next_permutation的操作原理，然后给这个题目推出了一个公式
但是对于我们这种，没法在短短十几分钟内把握整个题目全部操作的人，肯定很难一口气把公式给推出来
但是，我们可以打表
打表代码如下：

#include<bits/stdc++.h>using namespace std;//#define int long longconst int N = 1e8;int a[N];int b[N];int ans, cnt,sum,n;int32_t main(){ while(scanf("%d",&n)==1&&n!=-1){ ans = cnt = sum = 0; for (int i = 0; i < n; i++) a[i] = i+1; do { for (int i = 0; i < n; i++){ b[++cnt] = a[i]; } } while (next_permutation(a,a+n)); for (int i = 1; i<=cnt-n+1;i++){ sum = 0; for (int j = i; j <i+n;j++) sum += b[j]; if(sum==n*(n+1)/2) ans++; } cout << ans<<endl; } system("pause"); return 0;}

打表的时候有两个地方要提：
1.不用mod的话，我们开一个1e8的数组，最多可以显示到n=10的位置
再多就不行了
2.打表的结果：

现在来分析怎么得出一个菜鸟也能找出来的规律，而不是题解里的那种规律
n=1： ans=1；
n=2： ans=2;
n=3; ans=9=3!+3;
n=4; ans=56=4!+32;
n=5: ans=395=5!+275;

首先，为什么提出来一个i的阶乘？
因为题目是将1~n的数进行全排列，那么首先全排列的种类就是n！的阶乘个
所以最后的答案里面，肯定有一部分是属于n！的阶乘的
即使是傻瓜解法，也必须把这一步的原理给弄清楚，才可以继续往下找规律,不然傻瓜解法也救不了你

所以我们把这个答案给拆开了，拆成了n！和一个不知道是什么的数
接下来跟初中高中找规律是一样的，我们不从原理出发，只从式子本身出发，很容易发现一个规律。规律就在后面的代码里
不必多说了，毕竟这个原理我也说不清楚，只能用我这种笨方法来写
比赛的时候，如果要打表解决的话，注意的就是
别打错了...数组别开小了
其他的没什么好说的

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6+100;const int mod = 998244353;//ll factorial(ll a){// ll num=1;// for (ll i = 1; i <= a;i++)// num =(num * i) % mod;// return num;//}ll a[N];//这里储存之前的所有值，神秘递推式int main(){ ll n; cin >> n; a[1] = 1; ll fact = 1; for (ll i =2; i <= n;i++){ fact = fact * i % mod; a[i] = (i * (a[i - 1] - 1) + fact) % mod; } cout << a[n]; system("pause"); return 0;}

对于这个代码我还有个疑问，为什么我写的factorial函数通过不了呢？
输入1000000之后直接RE了，不输出数据
留待以后去解决；

其他的题解实在是看不懂，大家的思路都跟着官方题解走，但是又解释不清楚；
整篇题解的思路来自这个博主：hyacinthLJ
感谢！！万分感谢！！！