HihoCoder - 1801 :剪切字符串 (置换与逆序对)

时间:2020-12-28 23:45:40

Sample Input

6 5 11

Sample Output

6

小Hi有一个长度为N的字符串,这个字符串每个位置上的字符两两不同。现在小Hi可以进行一种剪切操作:

选择任意一段连续的K个字符,把这段子串剪下来,粘在串首或者串尾。例如ABCDE -> ADEBC、ABCDE -> BCADE或者ABCDE -> DEABC等。

小Hi想知道如果可以反复进行任意次剪切操作,他最多可能得到多少种不同的字符串。由于数目可能非常大,你只需要输出模P的余数即可。

Input

三个整数N, K和P。

1 ≤ K ≤ N ≤ 107, 1 ≤ P ≤ 109 P是质数

Output

一个整数代表答案。

思路:字符串可以看作是对应元素间形成的一个置换群,连续子串的剪切操作即乘上另一个置换。奇数长度对应的置换可以改变原置换逆序对数的奇偶性,而偶数长度对应的置换维持原有奇偶性不变。故当N=K时,答案为1,N=K+1时,答案为原串生成的循环串数量,答案为N,N>K+1时,K为奇数时答案为N!,偶数时答案为N!/2。

这里的逆序对,统计的是相对位置的逆序对,可以参考:https://blog.csdn.net/mygodhome/article/details/5902400

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main()
{
int N,K,P,ans=;
scanf("%d%d%d",&N,&K,&P);
if(N==K) ans=;
else if(N==K+) ans=N%P;
else if(K&) rep(i,,N) ans=1LL*ans*i%P;
else rep(i,,N) ans=1LL*ans*i%P;
printf("%d\n",ans);
return ;
}