Permutation Counting HDU - 3664

本文主要是介绍Permutation Counting HDU - 3664，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： HDU - 3664

题意:
给出数列a[]=1~n， 共n个数，在数列中如果ai>i(i是下标), val++; 问当val=k时有几种数列（即n个数顺序不同）
dp[i][j]=dp[i-1][j]*(j+1)+dp[i-1][j-1]*(i-j);
dp[i][j]表示第i个数前边有j个位置aj>j， 即val=j;
dp[i-1][j]->dp[i][j]增加了j*dp[i-1][j]个， dp[i-1][j-1]->dp[i][j]是有(i-j)种val+1的方式；
所以有dp[i][j]=dp[i-1][j]*(j+1)+dp[i][j]*(i-j);#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int N, k;
const long long mod=1e9+7;
long long dp[1005][1005];
int main(){dp[1][0]=1;for(int i=2; i<=1000; i++){for(int j=0; j<=i; j++){dp[i][j]=(dp[i-1][j-1]*(i-j)%mod+dp[i-1][j]*(j+1)%mod)%mod;}}while(cin >> N >> k){cout << dp[N][k] << endl;}return 0;
} 

这篇关于Permutation Counting HDU - 3664的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---