Cod sursa(job #1762788)

Utilizator Team_FII_AHreapca Buruiana Ionita Team_FII_A Data 24 septembrie 2016 09:44:13
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream fin("diapazon.in");
ofstream fout("diapazon.out");

const int dim = 205;
const int mod = 1000000007;
typedef pair<int, int> pii;

pii dp[2][dim][dim];

pii Add(pii a, pii b) {

    int num = (1LL * a.second * b.second) % mod;
    int nr = (1LL * a.first * b.second + 1LL * a.second * b.first) % mod;

    return pii(nr, num);

}

pii Prod(pii a, pii b) {

    int nr = (1LL * a.first * b.first) % mod;
    int num = (1LL * a.second * b.second) % mod;

    return pii(nr, num);

}

pii prob[dim];

int lef[dim], rig[dim];

pii Inv(pii a) {

    a.first = a.second - a.first + mod;
    a.first %= mod;

    return a;

}

void Euc(int a, int b, int &x, int &y) {

    if (!b) {
        x = 1, y = 0;
        return;
    }

    int xa, ya;
    Euc(b, a%b, xa, ya);

    x = ya;
    y = xa - (a/b)*ya;

}

int main() {

    int n;
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> lef[i] >> rig[i] >> prob[i].first >> prob[i].second;

    vector<int> vals;
    for (int i = 1; i <= n; ++i)
        vals.push_back(lef[i]), vals.push_back(rig[i]);


    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    int OLD= 0, NEW = 1;
    for (int l = 1; l <= (int)vals.size(); ++l)
            for (int r = 1; r <= (int)vals.size(); ++r)
                dp[OLD][l][r] = pii(0, 1);

    int l = lower_bound(vals.begin(), vals.end(), lef[1]) - vals.begin() + 1;
    int r = lower_bound(vals.begin(), vals.end(), rig[1]) - vals.begin() + 1;

    dp[OLD][l][r] = pii(1, 1);

    for (int i = 2; i <= n; ++i) {

        for (int l = 1; l <= (int)vals.size(); ++l)
            for (int r = 1; r <= (int)vals.size(); ++r)
                dp[NEW][l][r] = pii(0, 1);

        int ll = lower_bound(vals.begin(), vals.end(), lef[i]) - vals.begin() + 1;
        int rr = lower_bound(vals.begin(), vals.end(), rig[i]) - vals.begin() + 1;

        for (int l = 1; l <= (int)vals.size(); ++l)
            for (int r = l + 1; r <= (int)vals.size(); ++r) {

                if (r < ll || l > rr)
                    dp[NEW][l][r] = dp[OLD][l][r];
                else {

                    dp[NEW][min(l, ll)][max(r, rr)] = Add(dp[NEW][min(l, ll)][max(r, rr)], Prod(dp[OLD][l][r], prob[i]));
                    dp[NEW][l][r] =  Add(dp[NEW][l][r], Prod(dp[OLD][l][r], Inv(prob[i])));

                }

            }

            swap(NEW, OLD);

    }


    pii sol(0, 1);
    for (int l = 1; l <= (int)vals.size(); ++l)
            for (int r = l + 1; r <= (int)vals.size(); ++r) {

                if (dp[OLD][l][r].first == 0)
                    continue;

                pii temp(1LL * dp[OLD][l][r].first * (vals[r - 1] - vals[l - 1]) % mod, dp[OLD][l][r].second);
                Add(sol, temp);

            }

    int x, y;
    Euc(mod, sol.second, x, y);
    y %= mod;
    if (y < 0)
        y += mod;

    fout << 1LL * sol.first * y % mod << '\n';

    return 0;

}

//Trust me, I'm the Doctor!