【DP】一道递推题。。。

时间:2022-12-18 13:25:46

Bob想要构造一张由n个节点构成的图。构造的过程由两步组成:首先Bob会取出n个孤立的点,并把它们从1到n编号,然后对每个节点用一种颜色染色,Bob一共可以使用K种不同的颜色。接下来Bob会在这张图中加入一些有向边,对于每一个编号范围在[2,n]的节点i,Bob有可能选择一个节点j满足j < i并且节点i与j的颜色不同,然后加入一条从i到j的有向边,对于节点i,Bob也有可能不加任何的有向边。现在你需要回答Bob有可能构造出多少种不同的图。

 

输入:

第一行包含三个整数n,K。

 

输出:

输出一个整数占一行,表示对应的答案模10^9 + 7。

 

样例输入:

3 2

 

样例输出:

24

 

(所有的24种可能情况如下)

 【DP】一道递推题。。。

数据范围:

对于20%的数据,1 <= n <= 5,1 <= K <= 2。

对于100%的数据,1 <= n <= 10^6,1 <= K <= 10^6。


  看到题被吓尿了,感觉根本没法做,写了个暴搜,结果全错+T了。。。

  这个题比较考思维,其实要往递推方向想。我们假设dp[i]表示有i个点时所能够画出来的所有组合,那么我们来分析一下是结果是如何递推的。

  dp[i]无非由两部分组成,一部分是不连线的,一部分是连线的,对于不连线的,很简单,只需要dp[i-1]*k就行了,无需多说。

  那么连线的部分怎么办呢?我们可以连向前i-1个点,但是我们并不知道它们的具体颜色,但是我们只要保证连着的两个颜色不一样即可,那么对于第i个点往前连的时候,它能连的颜色只有(k-1)种,然后分步原理,再乘上i-1的组合总数就行了,所以连线的部分转移方程是(i-1)*(k-1)*dp[i-1]。所以总的状态转移方程是dp[i]=dp[i-1]*k+(i-1)*(k-1)*dp[i-1]。。。不仔细想真想不出来啊。。。

  那么代码如下:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstdlib>
 6 using namespace std;
 7 const long long MOD=1000000007;
 8 const int maxn=1000000+10;
 9 void init()
10 {
11     freopen("B.in","r",stdin);
12     freopen("B.out","w",stdout);
13     int size = 256 << 20; // 256MB
14     char *p = (char*)malloc(size) + size;
15     __asm__("movl %0, %%esp\n" :: "r"(p));
16 }
17 long long n,k;
18 long long dp[maxn];//i个节点,k种颜色,所有可能的组合总数
19 void read()
20 {
21     cin>>n>>k;
22 }
23 void work()
24 {
25     dp[0]=1;//一个节点都没有,是一种组合
26     for(long long i=1;i<=n;i++)
27     {
28         dp[i]=(k*dp[i-1]%MOD+((i-1)*(k-1))%MOD*dp[i-1]%MOD)%MOD;//递推方法:对于当前的dp[i],如果不连线,那么就有k种组合如果连线,那么有i-1个点可以连,但是要保证颜色不同,所以有k-1种颜色可以连,然后分步原理乘上i-1的组合总数 
29     }
30     printf("%I64d",dp[n]);
31 }
32 int main()
33 {
34     init();
35     read();
36     work();
37     return 0;
38 }