Description

一個數組A = [1, 2, 3, …, n]。

對A進行好恰好k次相鄰交換，能得到多少個不同的序列 (S1)？
對A進行最多k次交換，你能得到多少個不同的序列 (S2)？

一次相鄰交換是指交換數組A中兩個相鄰位置的元素，即：交換A[i]和A[i+1]或者A[i]和A[i-1]。
一次交換是指交換數組A中的任意兩個位置不同的元素，即：交換A[i]和A[j]，1 <= i, j <= N, i != j。

給出數組A的長度N，以及次數K，求S1和S2。由于結果很大，輸出Mod 1000000007的結果。
例如：原始數組: [1, 2, 3]

經過兩次相鄰交換:
我們得到 [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S1 = 3

經過最多兩次交換:
1) 0次交換后: [1, 2, 3]
2) 1次交換后: [2, 1, 3], [3, 2, 1], [1, 3, 2].
3) 兩次交換后: [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S2 = 6

Input

數組A的長度N，以及次數K。

Output

S1和S2。由于結果很大，輸出Mod 1000000007的結果。

Sample Input

5 10

Sample Output

60 120

Data Constraint

對于50%數據N,K<=500
對于100%數據1<=N, K<=3000

Solution

• 問題分為兩個子問題：恰好 k 次相鄰交換的排列數、最多 k 次交換排列數。

• 對于第一個子問題，設 F[i][j] 表示做到第 i 個數，交換次數為 j 能得到的排列數。

• 首先繼承上一個

  F[i][j]=f[i?1][j]

• 不過當 i 交換到第 1 個位置之后，再換就會算重，所以：

  F[i][i+j]?=F[i?1][j]

• 最后：

  F[i][j]+=F[i][j?1]

• (這里是不斷向前交換)。

• 這樣最后的答案就是 F[n][i]?(k?i是偶數) ，即剩下 k?i 步可以不斷的交換相鄰兩個來達到。

• 對于第二個子問題，就相對比較簡單了。

• 同樣設 F[i][j] 表示做到第 i 個數，交換次數為 j 能得到的排列數。

• 那么則有：

  F[i][j]=F[i?1][j]+F[i?1][j?1]?(i?1)

• 因為對于第 i 個數無非就是不交換或者與前 i?1 個數交換。

• 顯然答案即為：

  ∑i=0kF[n][i]

• 這樣兩個 DP 的時間復雜度都是 O(NK) ，則總復雜度為 O(NK) 可過本題。

Code

#include<cstdio> #include<cstring> using namespace std; const int mo=1e9+7; int n,k,roll,ans; int f[2][3002]; int main() {scanf("%d%d",&n,&k);for(int i=f[0][0]=1;i<=n;i++){roll^=1;memset(f[roll],0,sizeof(f[roll]));for(int j=0;j<=k;j++){f[roll][j]=((long long)f[roll][j]+f[roll^1][j]+f[roll][j-1])%mo;if(i+j<=k) f[roll][i+j]=(f[roll][i+j]+mo-f[roll^1][j])%mo;}}for(int i=0;i<=k;i++)if(!(k-i&1)) ans=(ans+f[roll][i])%mo;printf("%d ",ans);memset(f[0],ans=roll=0,sizeof(f[0]));for(int i=1;i<=n;i++){roll^=1;memset(f[roll],0,sizeof(f[roll]));f[roll][0]=1;for(int j=1;j<=k;j++)f[roll][j]=(f[roll^1][j]+(long long)f[roll^1][j-1]*(i-1))%mo;}for(int i=0;i<=k;i++) ans=(ans+f[roll][i])%mo;printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5253. 排列与交换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。