Skip to content

Instantly share code, notes, and snippets.

@edwardmjm edwardmjm/gist:9860831
Last active Aug 29, 2015

Embed
What would you like to do?
#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);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.