제출 #1334657

#제출 시각아이디문제언어결과실행 시간메모리
1334657nhan0123456Fancy Fence (CEOI20_fancyfence)C++17
40 / 100
22 ms2000 KiB
#include <bits/stdc++.h>
using namespace std;
bool memory1;

typedef long long ll;
typedef unsigned long long ull;
typedef double dbe;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;

#define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
#define FOR(i, a, b, x) for (ll i = (a); i <= (b); i += (x))
#define ROF(i, a, b, x) for (ll i = (a); i >= (b); i += (x))
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define getBit(mask, i) (((mask) >> (i)) & 1LL)
#define BitOn(mask) (__builtin_popcountll(mask))

const int maxN = 1e5 + 5;
//const ll maxBit = MASK(8) + 2;
const ll LOG = 20;
const ll INF18 = 1e18;
const int INF9 = 1e9;
//const ll INF3f = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;

//////////////////////////////////////////////
/////////////////nhan0123456//////////////////
//////////////////////////////////////////////

ll n;
pll a[maxN];

ll powMod(ll a, ll b, const ll c) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1) ans = ans * a % c;
        a = a * a % c;
        b = b >> 1;
    }
    return ans;
}

namespace sub4 {
    bool check() {
        FOR (i, 1, n, 1) if (a[i].fi != a[1].fi) return false;
        return true;
    }
    ll Solve() {
        ll sumW = 0;
        FOR (i, 1, n, 1) (sumW += a[i].se) %= MOD;

        ll t1 = (sumW + sumW * (sumW - 1) % MOD * powMod(2, MOD - 2, MOD) % MOD) % MOD;
        ll t2 = (a[1].fi + a[1].fi * (a[1].fi - 1) % MOD * powMod(2, MOD - 2, MOD) % MOD) % MOD;
//        return (t * powMod(2, a[1].fi - 1, MOD) - 1 + MOD) % MOD;
        return t1 * t2 % MOD;
    }
}

namespace sub3 {
    bool check() {
        FOR (i, 1, n, 1) if (a[i].fi > 2) return false;
        return true;
    }
    ll Solve() {
        ll ans = 0;
        ll d = 0;
        ll sumW = 0;
        FOR (i, 1, n, 1) {
            ans += sumW * a[i].se;
            ans %= MOD;
            ans += a[i].se + a[i].se * (a[i].se - 1) % MOD * powMod(2, MOD - 2, MOD) % MOD;
            ans %= MOD;
            if (a[i].fi == 2) {
                d += a[i].se;
                d %= MOD;
            }
            else {
                ans += (d * 2 + d * (d - 1) % MOD) % MOD;
                d = 0;
            }
            ans %= MOD;
            (sumW += a[i].se) %= MOD;
        }
        ans += (d * 2 + d * (d - 1) % MOD) % MOD;
        ans %= MOD;
        return ans;
    }
}

namespace sub2 {
    ll s[55][55];
    bool check() {
        if (n > 50) return false;
        FOR (i, 1, n, 1) {
            if (a[i].fi > 50) return false;
            if (a[i].se != 1) return false;
        }
        return true;
    }
    ll Solve() {
        FOR (i, 1, n, 1) FOR (x, 1, a[i].fi, 1) s[i][x] = 1;
        FOR (i, 1, 50, 1)
        FOR (j, 1, 50, 1)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        ll ans = 0;
        FOR (x1, 1, 50, 1)
        FOR (y1, 1, 50, 1)
        FOR (x2, x1, 50, 1)
        FOR (y2, y1, 50, 1) {
            ll tt = (x2 - x1 + 1) * (y2 - y1 + 1);
            if (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] == tt)
                ++ans;
        }
        return ans;
    }
}

void input() {
    /*
        dem so hcn
        hi.. wi
    */
    cin >> n;
    FOR (i, 1, n, 1) cin >> a[i].fi;
    FOR (i, 1, n, 1) cin >> a[i].se;
    if (sub2::check()) cout << sub2::Solve();
    else if (sub3::check()) cout << sub3::Solve();
    else if (sub4::check()) cout << sub4::Solve();

}

int main() {
    //openFile("temp");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    input();

    //bool memory2;
    //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
    //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...