Brief description:
DIV 1 950. ProductQuery:
一个待定的长度为 n 的模 10 数组，一组询问 (l, r, o)，表示从第 l 位连乘到第 r 位的结果是 o .. .
要求给定 m 组询问之后还原此数组的可能组数。
(n ≤ 100, m ≤ 50 )
Analysis:
询问之间存在互相嵌套的关系，开线段树又无从下手，考虑肢解问题。
（显然从数论角度开始 yy。。） 对于模 p 数组，询问 (l, r, o): o = 0, 则 [l, r] 区间至少存在一个 0 o = x, 则 [l, r] 区间不能出现 0，最后一位总能找到一个逆元。
（对 10 分解后很自然会形成 模2 和 模5 两个子问题。。）
考虑一般的模 p 版本的子问题，观察后发现，对单个数只存在三种状态 ：
0 [1, p) 任何一个数 [1, p) 中的某一个数（被各种等式固定住了。）
对于 0 的情况可以立刻判断出来，对后两种情况，可以固定任意一个数位后判断是否存在矛盾。
（因为对于状态 3，如果确实是某一个数。。可以通过默认一个数位后把这个数显示的通过等式表示出来。。）
。。。这样设计 dp[i] 表示第 i 个位置如果是 0 的时候存在的所有方案数，（在数组末尾再添加一个默认为 0 的虚坷垃以记录所有方案。）。。枚举的时候找前面其他可能是 0 的位置，然后累计 Count(l, r) 表示 l, r 区间所有的数都是状态 2 和状态 3 所可能的方案数。。
（。。这样就不存在询问之间的嵌套影响。。Count 函数返回的结果会是 p-1 的某个整次幂 或者 不合法返回 0。。）
总的复杂度大概是 O(n2m) 吧..
const int N = 50;
DB dp[N][N][N][N];
class RandomColoring {
public:
double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) {
RST(dp), dp[0][startR][startG][startB] = 1;
#define u dp[i][r][g][b]
#define v dp[i+1][r+dr][g+dg][b+db]
REP(i, N) REP(r, maxR) REP(g, maxG) REP(b, maxB) if (u){
int S = 0;
FOR(dr, max(-r, -d2), min(maxR-r, d2+1)) FOR(dg, max(-g, -d2), min(maxG-g, d2+1)) FOR(db, max(-b, -d2), min(maxB-b, d2+1)){
if (abs(dr) < d1 && abs(dg) < d1 && abs(db) < d1) continue;
++S;
}
FOR(dr, max(-r, -d2), min(maxR-r, d2+1)) FOR(dg, max(-g, -d2), min(maxG-g, d2+1)) FOR(db, max(-b, -d2), min(maxB-b, d2+1)){
if (abs(dr) < d1 && abs(dg) < d1 && abs(db) < d1) continue;
v += u / S;
}
}
DB res = 0; int i = N - 1; REP(r, maxR) REP(g, maxG) REP(b, maxB) if (u){
if (abs(r - startR) > d2 || abs(g - startG) > d2 || abs(b - startB) > d2 ||
abs(r - startR) < d1 && abs(g - startG) < d1 && abs(b - startB) < d1)
res += u;
}
return res;
}
};
const int N = 50;
DB dp[N][N][N][N], s[N+1][N+1][N+1];
int w[N][N][N], maxR, maxG, maxB;
DB sum(int x0, int y0, int z0, int x1, int y1, int z1){
checkMin(++x1, maxR), checkMin(++y1, maxG), checkMin(++z1, maxB), checkMax(x0, 0), checkMax(y0, 0), checkMax(z0, 0);
return s[x1][y1][z1] - s[x0][y1][z1] - s[x1][y0][z1] - s[x1][y1][z0] + s[x0][y0][z1] + s[x0][y1][z0] + s[x1][y0][z0] - s[x0][y0][z0];
}
class RandomColoring {
public:
double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) {
::maxR = maxR, ::maxG = maxG, ::maxB = maxB;
RST(dp, w, s), dp[0][startR][startG][startB] = 1;
REP_1(r, maxR) REP_1(g, maxG) REP_1(b, maxB) s[r][g][b] = r * g * b;
REP(r, maxR) REP(g, maxG) REP(b, maxB) w[r][g][b] = sum(r-d2, g-d2, b-d2, r+d2, g+d2, b+d2) - (d1 ? sum(r-d1+1, g-d1+1, b-d1+1, r+d1-1, g+d1-1, b+d1-1) : 0);
#define u dp[i][r-1][g-1][b-1]
#define w w[r-1][g-1][b-1]
#define v dp[i+1][r][g][b]
--N; REP(i, N){
REP_1(r, maxR) REP_1(g, maxG) REP_1(b, maxB) {
if (u && w) u /= w;
s[r][g][b] = u + s[r-1][g][b] + s[r][g-1][b] + s[r][g][b-1] - s[r-1][g-1][b] - s[r-1][g][b-1] - s[r][g-1][b-1] + s[r-1][g-1][b-1];
}
REP(r, maxR) REP(g, maxG) REP(b, maxB){
v = sum(r-d2, g-d2, b-d2, r+d2, g+d2, b+d2) - (d1 ? sum(r-d1+1, g-d1+1, b-d1+1, r+d1-1, g+d1-1, b+d1-1) : 0);
}
}
#undef u
#define u dp[i][r][g][b]
DB res = 0; int i = N; REP(r, maxR) REP(g, maxG) REP(b, maxB) if (u){
if (abs(r - startR) > d2 || abs(g - startG) > d2 || abs(b - startB) > d2 ||
abs(r - startR) < d1 && abs(g - startG) < d1 && abs(b - startB) < d1)
res += u;
}
return res;
}
};
const int Null = -1;
const int N = 109;
VI L, R, O; VII adj[N];
int A[N], n, m, mod;
int _I(int x){
FOR(i, 1, mod) if (i * x % mod == 1) return i;
}
#define v adj[u][i].first
#define r adj[u][i].second
bool dfs(int u, int val) {
if (A[u] == Null) A[u] = val; else return A[u] == val;
REP(i, SZ(adj[u])) if (!dfs(v, (u <= v ? r : _I(r)) * val % mod)) return false;
return true;
}
#undef v
#undef r
int count(int l, int r) {
if (r - l <= 0) return 1;
REP(i, m){
int a = L[i], b = R[i], o = O[i] % mod;
if (!o && l <= a && b < r) return 0;
}
FOR_1(i, 0, n+1) CLR(adj[i]);
REP(i, m){
int a = L[i], b = R[i] + 1, o = O[i] % mod;
if (a >= l && b <= r){
adj[a].PB(MP(b, o));
adj[b].PB(MP(a, o));
}
}
int cnt = -1; FLC(A, Null);
for (int i = l; i <= r; ++i) {
if (A[i] == Null) {
if (!dfs(i, 1)) return 0;
++cnt;
}
}
return pow(mod-1, cnt);
}
int dp[N]; bool Z[N]; // could be zero ?
LL calc(int mod) {
FLC(Z, true), ::mod = mod; REP_1(i, n) REP(j, m){
int l = L[j], r = R[j], o = O[j] % mod;
if (o && l <= i && i <= r){Z[i] = false; break;}
}
RST(dp), dp[0] = 1;
REP_1(i, n + 1) if (Z[i]){
REP(l, i) if (Z[l]) INC(dp[i], pdt(dp[l], count(l + 1, i))); //[l+1, i)
}
return dp[n+1];
}
class ProductQuery {
public:
int theInput(int N, vector<int> Qfrom, vector<int> Qto, vector<int> output) {
n = N, m = SZ(Qfrom), L = Qfrom, R = Qto, O = output; REP(i, m) ++L[i], ++R[i];
return pdt(calc(2), calc(5));
}
};
