题意
定义permutation，里面要有1到n所有数字，并且每个数字唯一。定义([l,r], 1leq lleq rleq n), 为从l到r的subsegment。
定义framed segment: (max{ p_l,p_{l+1},…,p_r }−min{ p_l,p_{l+1},…,p_r }=r−l.)的 ([l,r]),([i,i])是framed segment。
定义p的快乐值: ((l,r))的数量，其中(1leq lleq rleq n, [l,r]是framed segment)
给你一个n,MOD。让你求n长的permutation的快乐值，并模MOD。
思路
- 组合数学推一下公式
- 枚举framed segment的长度(len = r-l+1)。
- (ans = (sum_{len=1}^n{C_{n-len+1}^1 * (len)!*C_{n-len+1}^1*(n-len)!})\%MOD)
- (C_{n-len+1}^1): 从n-len+1中选个一个数字作为这个framed segement的最小值，最小值确定了，len确定了，r-l就确定了，最大值也就确定了。n-len+1因为最大值也要在<=n。
- (len!): 这个framed segment内部的全排列。
- (C_{n_len+1}^1): 给这个framed segment选一个位置。
- ((n-len)!): 剩下的元素排列一下。
- 简化，发现实际上可以把framed segment整个看成一个，(C_{n-len+1}^1*(n-len)!=(n-len+1)!)
- 所以(ans = (sum_{len=1}^n{(n-len+1)*(len)!*(n-len)!})\%MOD)
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=250005;
typedef long long ll;
ll fac[MAXN];
int main(){
ll n;
int m;
scanf("%lld%d",&n,&m);
ll ans=0;
fac[0]=1;
for(ll i=1;i<=n;i++){
fac[i]=(fac[i-1]*i)%m;
}
for(ll i=1;i<=n;i++){
ans=(ans+((((n-i+1)*fac[i])%m)*fac[n-i+1])%m)%m;
}
printf("%lld
",ans);
return 0;
}