HDU 5622 KK's Chemical

17031 단어 HDU
문제 설명
     KK          :    N\left(1\leq N\leq 100 \right)N(1N100)00 N-1N1,  KK   i       c[i]c[i]           。KK          ,        k       。  ,  KK     ,                     。  KK            。             ,        {10}^{9}+7109+7c[i] 
eq i
c[i]i

입력 설명
      T\left( 1\leq T\leq 200\right)T(1T200),      。
      ,       N\left(1\leq N\leq 100 \right)N(1N100) K\left(1\leq K\leq 1000 \right)K(1K1000),                  。
      NN   c[i]\left( 0\leq c[i]\leq N-1\right)c[i](0c[i]N1)

출력 설명
{10}^{9}+7109+7

입력 샘플
3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0

출력 샘플
6
12

0

t t , ,

, k ,

dp , k-1

dfs

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, n, m, x, dis[maxn], loop, cnt;
LL dp[maxn], f[maxn];
vector<int> t[maxn];

void dfs(int x, int dep, int fa)
{
    dis[x] = dep;    cnt++;
    for (int i = 0; i < t[x].size(); i++)
    if (t[x][i] != fa)
    {
        if (dis[t[x][i]] && dis[t[x][i]] < dep) loop = dep - dis[t[x][i]] + 1;
        if (!dis[t[x][i]]) dfs(t[x][i], dep + 1, x);
    }
}

int main(){
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        if (m == 1) { printf("%d
", n - 1 ? 0 : 1); continue; } dp[1] = m; dp[2] = m*(m - 1); dp[3] = m*(m - 1)*(m - 2); f[0] = 1; for (int i = 4; i <= n; i++) dp[i] = ((m - 2)*dp[i - 1] + (m - 1)*dp[i - 2]) % mod; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (m - 1) % mod; for (int i = 0; i < n; i++) t[i].clear(), dis[i] = 0; for (int i = 0; i < n; i++) { scanf("%d", &x); t[x].push_back(i); t[i].push_back(x); } LL ans = 1; for (int i = 0; i < n; i++) { if (dis[i]) continue; loop = cnt = 0; dfs(i, 1, i); if (!loop) loop = 2; (ans *= f[cnt - loop] * dp[loop] % mod) %= mod; } cout << ans << endl; } return 0; }

좋은 웹페이지 즐겨찾기