제출 #956382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956382		Ariadna	Relativnost (COCI15_relativnost)	C++14	0 / 140	4099 ms	11348 KiB

relativnost

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e4+7;

int ways(int i, int n, vector<int>& a, vector<int>& b, int colour, int c, int total) {
    if (i == n) {
        if (colour < c) return 0;
        return total % mod;
    }
    if (n-i < c-colour) return 0;
    return (ways(i+1, n, a, b, colour+1, c, (total * a[i]) % mod) + ways(i+1, n, a, b, colour, c, (total*b[i]) % mod)) % mod;
}

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        a[i] %= mod;
        b[i] %= mod;
    }
    int ans = -1;
    int q;
    cin >> q;
    while (q--) {
        int i, a_, b_;
        cin >> i >> a_ >> b_; 
        --i;
        if (a_ != a[i] || b_ != b[i] || ans == -1) {
            a[i] = a_; b[i] = b_;
            ans = ways(0, n, a, b, 0, c, 1) % mod;
        }
        cout << ans << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 140