20161115测试总结

#include <bits/stdc++.h>
const int mod = 1e9 + 7;
typedef long long ll;
const int sig = 2e9;
inline ll mul(ll a, ll b, ll c) {
    a %= c, b %= c;
    return c <= sig ? (a * b % c + c) % c : (a * b - (ll)(a / (long double)c * b) * c + c) % c;
}
inline ll modPow(ll a, ll b) {
    register ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = mul(ans, a, mod);
        a = mul(a, a, mod);
    }
    return ans;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("calc.in", "r", stdin);
#endif
    using namespace std;
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, m;
    cin >> n >> m;
    cout << ((modPow(m, n + 1) - 1) * modPow(m - 1, mod - 2)) % mod;
    return 0;
}

#include <bits/stdc++.h>
#include <tr1/unordered_map>
std::tr1::unordered_map<int, int> rcnt, ccnt;
std::tr1::unordered_map<int, int> rxor, cxor;
std::map<std::pair<int, int>, int> rook;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
inline void read(int &x) {
    for (ioc = read(); !isdigit(ioc); ioc = read());
    x = 0;
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    if (iosig) x = -x;
}
int n, k, q;
const int MAXN = 10010;
long long sol;
inline void moveRook(int r, int c, int val) {
    using namespace std;
    register int Rxor = rxor[r], Cxor = cxor[c];
    sol -= n - ccnt[Rxor];
    sol -= n - rcnt[Cxor];
    if (Rxor != Cxor)
        sol++;
    rcnt[Rxor]--;
    Rxor = rxor[r] ^= val;
    rcnt[Rxor]++;
    ccnt[Cxor]--;
    Cxor = cxor[c] ^= val;
    ccnt[Cxor]++;
    sol += n - ccnt[Rxor];
    sol += n - rcnt[Cxor];
    if (Rxor != Cxor)
        sol --;
    rook[make_pair(r, c)] ^= val;
}
inline void init() {
    read(n), read(k), read(q);
    rcnt[0] = ccnt[0] = n;
    for (register int i = 0; i < k; i++) {
        register int r, c, val;
        read(r), read(c), read(val);
        r--, c--;
        moveRook(r, c, val);
    }
}
inline void solve() {
    using namespace std;
    while (q--) {
        register int r1, c1, r2, c2;
        read(r1), read(c1), read(r2), read(c2);
        r1--, c1--, r2--, c2--;
        register int rookValue = rook[make_pair(r1, c1)];
        moveRook(r1, c1, rookValue);
        moveRook(r2, c2, rookValue);
        cout << sol << "\n";
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("chess.in", "r", stdin);
#endif
    using namespace std;
    init();
    solve();
    return 0;
}

#include <bits/stdc++.h>
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
inline void read(int &x) {
    for (ioc = read(); !isdigit(ioc); ioc = read());
    x = 0;
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
}
const int MAXN = 100005;
int a[MAXN];
int n, m;
struct SegmentTree {
    int min[MAXN << 2], now, ll, rr, val;
    inline void build(int x, int l, int r) {
        if (l == r) {
            min[x] = a[l];
            return;
        }
        register int mid = l + r >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        if (min[x << 1] < min[x << 1 | 1]) min[x] = min[x << 1];
        else min[x] = min[x << 1 | 1];
    }
    inline void query(int x, int l, int r) {
        if (min[x] > now) return;
        if (val <= rr) return;
        if (l >= ll && r <= rr) {
            if (l == r) {
                val = l;
                return;
            }
            register int mid = l + r >> 1;
            query(x << 1, l, mid);
            query(x << 1 | 1, mid + 1, r);
            return;
        }
        register int mid = l + r >> 1;
        if (rr <= mid) query(x << 1, l, mid);
        else if (ll > mid) query(x << 1 | 1, mid + 1, r);
        else query(x << 1, l, mid), query(x << 1 | 1, mid + 1, r);
    }
    inline void solve() {
        read(ll), read(rr), now = a[ll];
        for (ll++; now && ll <= rr;) {
            val = n + 1;
            query(1, 1, n);
            if (val > rr) break;
            now %= a[val], ll = val + 1;
        }
        std::cout << now << "\n";
    }
} tree;
int main() {
#ifndef ONLINE_JUDGE
    freopen("function.in", "r", stdin);
#endif
    read(n);
    for (register int i = 1; i <= n; i++) read(a[i]);
    tree.build(1, 1, n);
    read(m);
    while (m--)
        tree.solve();
    return 0;
}