题面在这里
考虑把1到n的数一个一个加入，这样状态比较好设计
对于第一问：
\(f_{i,j}\)表示长度为\(i\)的排列，恰好做了\(j\)次交换
\[
f_{i,j}=\sum_{k=max(0,j-i+1)}^j f_{i-1,k}
\]
因为可以两个数不断交换，答案是\(\sum_{j\text{ mod }2=m\text{ mod }2} f_{n,j}\)
对于第二问：
\(g_{i,j}\)表示长度为\(i\)的排列，恰好做了\(j\)次交换 \[
g_{i,j}=g_{i-1,j}+(i-1)\cdot g_{i-1,j-1}
\] 答案是\(\sum_j g_{n,j}\)
示例程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=3005,MOD=1e9+7;
int n,K,f[maxn][maxn],g[maxn][maxn],s[maxn][maxn],ans;
#define up(x,y) ((x+=y)%=MOD)
int main(){
scanf("%d%d",&n,&K);
f[0][0]=1;
for (int j=0;j<=K;j++) s[0][j]=1;
for (int i=1;i<=n;i++){
for (int j=0;j<=K;j++)
up(f[i][j],s[i-1][j]-(j>=i?s[i-1][j-i]:0)),
s[i][j]=((j==0?0:s[i][j-1])+f[i][j])%MOD;
}
ans=0;
for (int j=0;j<=K;j++) if (j%2==K%2) up(ans,f[n][j]);
printf("%d ",ans);
g[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=0;j<=K;j++)
up(g[i][j],(g[i-1][j]+(ll)(j==0?0:g[i-1][j-1])*(i-1))%MOD);
ans=0;
for (int j=0;j<=K;j++) up(ans,g[n][j]);
printf("%d",ans);
return 0;
}
|
