http://codeforces.com/problemset/problem/1081/C
题意:有n个排成一行板块,有m种颜色,要让这些板块有k对相邻板块不同颜色,有多少种涂色方法?
比如样例2,3块板,2种颜色,1对不同。有4种涂法。[ 1 2 3 ]表示板块位置。
1.黄+绿+绿
2.黄+黄+绿
3.绿+黄+黄
4.绿+绿+黄
为什么是相邻不同?百度翻译讲得含糊其辞。从样例可以推断出来如果第1种情况种,第一个黄 越过第二个绿 直接与第三个绿构成一种情况,则样例不成立。
解题:
dp[i][j]表示长度为i的板块中有j个不同色的情况。
对于第1个板块,肯定是没有不同色的,1个哪来的不同?第1个板块的涂色方法有m种,这应该可以理解,每种颜色都可以涂在第1块上,暂时不考虑其他的东西。
举例:有4块板,3种颜色(用字母a,b,c表示),要2种不同色。
对于第1个板块,有3种情况
a * * *
b * * *
c * * *
本例子要求2个相邻不同色
则对于第2个板块,要创造出1个相邻不同色,则第二个板块要和前面的板块不同色,前面的板块占m种中的1种,则与它不同色的情况有m-1种。dp[i][j] = dp[i-1][j-1] *(m-1)。比如现在的dp[2][1]=dp[1][0]*2=3*2=6;
a b * * a c * *
b a * * b c * *
c a * * c b * *
对于第3个板块,如果要再创造出1个相邻不同色,则dp[3][2]=dp[2][1]*2=6*2=12;
aba* abc* aca* acb*
bab* bac* bca* bcb*
cac* cab* cba* cbc*
对于第4个板块,2个相邻不同色已经够了,则不需要再创造相邻不同色了,按照上一种涂色方法继续涂就好。dp[i][j]=dp[i-1][j];
abaa abcc acaa acbb
babb bacc bcaa bcbb
cacc cabb cbaa cbcc
但是,如果第2块涂的时候不创造相邻不同色,则是这样,dp[i][j]=dp[i-1][j],dp[2][0]=dp[1][0]。
aa**
bb**
cc**
不创造相邻不同色是在已经有足够相邻不同色的情况下派上用场。
接下来第3块想创造1个相邻不同色则还是 dp[i][j]=dp[i-1][j-1]*(m-1)
aab* aac*
bba* bbc*
cca* ccb*
所以状态转移方程是
dp[i][j]=dp[i-1][j-1]*(m-1) + dp[i-1][j];
记得求模,随便模。
类似那些dp[1][1],dp[2][2]这种不可能存在的东西当作0处理就可以了,1块板1个不同???2块板2个不同???
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<map> #include<string> #define ll long long #define inf 0x3f3f3f3f using namespace std; ll n,m,k; ll dp[2222][2222]; ll p=998244353; int main() { while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][0]=m;///没有不同则是全部板都是一种颜色,无论板多长 for(int i=2;i<=n;i++) for(int j=1;j<=k;j++) dp[i][j] = ( dp[i-1][j-1]*(m-1)%p + dp[i-1][j] )%p; printf("%lld\n",dp[n][k]); } return 0; }dp解法
组合数解法:
k个相邻不同色,至少需要k+1个板块来完成。
对于第1个板块,有m种可能。
剩下还有n-1个板块,在拿出k个板块来和第1个一起创造k个相邻不同色,任取k个,C( n-1,k )。
对于后面这所有的板块,有2种情况。
1.属于k个板块之一,则要与上一个板块不同,才能创造相邻不同色,它有(m-1)种涂色方法。
2.不属于k个板块之一,那么要与上一个板块相同,不变!不需要乘什么乱七八糟的东西。
公式: m * C( n-1,k ) * (m-1)^k
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<map> #include<string> #define ll long long #define inf 0x3f3f3f3f using namespace std; ll n,m,k; ll p=998244353; ll C[2222][2222];///C[i][j]表示从i个里拿j个 void init() { memset(C,0,sizeof(C)); for(int i=0;i<2222;i++) C[i][0]=C[i][i]=1; for(int i=1;i<2222;i++) for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;///组合恒等式 /* for(int i=0;i<=10;i++) { for(int j=0;j<=i;j++) printf("%5lld",C[i][j]); printf("\n"); }*/ } int main() { init(); while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF) { ll ans=m*C[n-1][k]%p; for(int i=1;i<=k;i++) ans=ans*(m-1)%p; printf("%lld\n",ans); } return 0; }组合数解法