CodeAction_beta02 斐波那契 （多维DP）

时间：2023-03-09 00:24:57
CodeAction_beta02 斐波那契 （多维DP）

题面：

CodeAction_beta02 斐波那契 （多维DP）

CodeAction_beta02 斐波那契 （多维DP）

solution:

这题和斐波那契数列没有任何关系！！！！！

这题就是一个无脑DP！！！！！！！！！！

因为所有数都要出现至少一次，所以只需考虑其组合而不用考虑其排列，最后乘个 n!就是了(意思就是可以当做这 N 个数是无序的)

dp[i][j]表示前 i 个序列放了 j 种数的方案数，所以在放第 i+1 个数的时候有两种选择

  1. 放一个新的数 则状态变到 dp[i+1][j+1]
  2. 放一个前面有的数 则状态变到 dp[i+1][j]

    对于第一种转移情况有 dp[i+1][j+1]+=dp[i][j]

    而对于第二种转移情况 为了满足最小间隔的要求 所以序列末尾的 M 种数是不可以放

    的 因此可供选择的数有(j-M)种 即 dp[i+1][j] += dp[i][j](j-M)

    算完之后 dp[P][N]    N!就是结果

code：

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

#define mod 1000000007

using namespace std;

int n,m,l;

ll ans=1;

ll f[1005][1005];

inline int qr(){

	char ch;

	while((ch=getchar())<'0'||ch>'9');

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res;

}

int main(){

	//freopen("pf.in","r",stdin);

	//freopen("pf.out","w",stdout);

	n=qr(),m=qr(),l=qr();

	f[1][1]=1;

	for(rg i=1;i<l;++i){

		for(rg j=1;j<=n;++j){

			if(!f[i][j])continue;

			if(j<n)f[i+1][j+1]+=f[i][j];

			if(j>m)f[i+1][j]+=f[i][j]*(j-m)%mod;

		}

	}ans=f[l][n];

	for(rg i=1;i<=n;++i)

		ans=ans*i%mod;

	printf("%lld",ans);

	return 0;

}

相关文章