gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define foreach(it, v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) __typeof((v).end())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
const int Mod = 1000000007;
int f[1000005][2];
int f2[1000005][2];
int g[55][2];
ll K;

void init() {
    clr(f, 0);
    clr(f2, 0);
    f[0][1] = 1;
    f[1][1] = K - 1;
    for (int i = 2; i <= 1000000; i++) {
        f[i][0] = f[i - 1][1];
        f[i][1] = (f[i - 1][0] * (K - 1) % Mod + f[i - 1][1] * (K - 2) % Mod) % Mod;
    }
    f2[0][1] = 1;
    f2[1][1] = K - 2;
    f2[1][0] = 1;
    for (int i = 2; i <= 1000000; i++) {
        f2[i][0] = f2[i - 1][1];
        f2[i][1] = (f2[i - 1][1] * (K - 2) % Mod + f2[i - 1][0] * (K - 1) % Mod) % Mod;
    }
}

int diff(int x, int y, int n) {
    if (x <= y) return y - x - 1;
    return y + n - x - 1;
}

bool near(int x, int y, int n) {
    return diff(x, y, n) == 0 || diff(y, x, n) == 0;
}

void add(int &t, ll x) {
    x %= Mod;
    t += x;
    t %= Mod;
}

ll countLink(int x, int y, int n, bool o /*same or not*/) {
    if (o) {
        if (near(x, y, n)) return 0;
        return f[diff(x, y, n)][1] * (ll)f[diff(y, x, n)][1] % Mod;
    } else {
        return f2[diff(x, y, n)][1] * (ll)f2[diff(y, x, n)][1] % Mod;
    }
}

int gao(vector <int> c, vector <int> St, vector <int> Ed, ll K) {
        ::K = K;
        set <int> s[55];
        int n = c.size();
        rep (i, n) {
            int j = (i + 1) % n;
            s[i].insert(St[i]);
            s[j].insert(Ed[i]);
        }
        init();
        clr(g, 0);
        int cnt = 0;
        if (s[0].size() == 1) {
            g[0][0] = K * f[c[0] - 1][1] % Mod;
        } else {
            int x = *s[0].begin();
            int y = *++s[0].begin();
            g[0][0] = K * countLink(x, y, c[0], 1) % Mod;
            g[0][1] = K * (K - 1) % Mod * countLink(x, y, c[0], 0) % Mod;
        }
        rep (d, n) {
            if (!d) continue;
            if (s[d].size() == 2) {
                int x = *s[d].begin();
                int y = *++s[d].begin();
                ll tmp = countLink(x, y, c[d], 1);
                add(g[d][0], tmp * g[d - 1][0] % Mod);
                add(g[d][1], tmp * g[d - 1][1] % Mod);
                tmp = countLink(x, y, c[d], 0);
                add(g[d][0], g[d - 1][1] * tmp % Mod);
                add(g[d][1], g[d - 1][1] * tmp % Mod * (K - 2) % Mod + g[d - 1][0] * tmp % Mod * (K - 1) % Mod);
            } else {
                ll tmp = f[c[d] - 1][1];
                add(g[d][1], g[d - 1][1] * tmp % Mod);
                add(g[d][0], g[d - 1][0] * tmp % Mod);
            }
        }
        return g[n - 1][0];
}

class CycleColoring { 
    public: 
    int countColorings(vector <int> c, vector <int> st, vector <int> ed, int K)  { 
        return gao(c, st, ed, K);
    } 
};