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));
    }
};

Posted by xiaodao
Category: TopCoder
Tags: 数论