每日一题4月7

题意：构成连通块的方案数
思路：用dp[i][j]表示前i个节点用j种颜色的方案,dp[i][j]是由他上一个节点的颜色相同方案加上他与上一节颜色方案不同的和dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(m-(j-1))

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
const int MAX =2e5+20;
const double PI = 3.14159265359;
const int mod=1e9+7;
int n,m;
int dp[666][666];
int main()
{
    SIS;
    cin>>n>>m;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(m-(j-1));
            dp[i][j]%=mod;
        }
    }
    ll res=0;
    for(int i=1;i<=m;i++)
        res=(res+dp[n][i])%mod;
    cout<<res<<endl;

    return 0;

}