hdu 6143 Killer Names dp

2024-04-07 03:58

文章标签 dp hdu killer names 6143

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

题目传送门：

题意：给出一个m个字母的字母表，问我们能生成多少对字符串，该对字符串长度为n。并且字符串之间不能存在相同的字母

思路1：用容斥原理推出状态转移方程dp[i][j]=dp[i-1][j]*i+dp[i-1][j-1]*i；

ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const long long mod=1e9+7;
long long C[2005][2005];
long long dp[2005][2005];
long long m,n;
void get_C()
{C[0][0] = 1;for(int i=1;i<=2000;i++){C[i][0] = 1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
}
long long quickmod(long long a,long long b)
{long long ans=1;a%=mod;while(b>0){if(b%2==1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;
}
void get_dp()
{for(int i=1;i<=2000;i++)dp[i][1]=1;for(long long i=2;i<=2000;i++){for(long long j=i;j<=2000;j++){dp[j][i]=((dp[j-1][i]*i)%mod+(dp[j-1][i-1]*i)%mod)%mod;}}
}
int main()
{int t;get_C();get_dp();scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&m);long long ans=0;for(long long i=1;i<m;i++){if(i>n)break;for(long long j=i;j+i<=m;j++){if(j>n)break;long long p=C[m][i]*dp[n][i]%mod;long long q=C[m-i][j]*dp[n][j]%mod;long long sum=(p*q)%mod;if(j!=i)ans=(ans+2*sum)%mod;elseans=(ans+sum)%mod;}}printf("%lld\n",ans);}return 0;
}

思路2：dp[i][j]表示用j中颜色去涂i个格子（j中颜色全用上），然后直接dp。状态转移方程为：dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(m-(j-1));

ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 2010;ll dp[maxn][maxn];ll quick_pow(ll a, ll n) {ll ans = 1;while (n) {if (n & 1)    ans = ans*a%mod;a = a*a%mod;n >>= 1;}return ans;
}int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);dp[1][1]=m;for(int i=2;i<=n;i++){for(int j=1;j<=i&&j<=m;j++){dp[i][j]=(dp[i-1][j]*j%mod+dp[i-1][j-1]*(m-j+1)%mod)%mod;}}ll ans=0;for(int i=1;i<m;i++){ans=(ans+dp[n][i]*quick_pow(m-i,n)%mod)%mod;}printf("%lld\n",ans);}return 0;
}