fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "PLAN"
  5.  
  6. using ll = long long;
  7.  
  8. const int M = 1e9;
  9.  
  10. inline ll addmod(ll a, ll b) {
  11.     a += b;
  12.     if (a >= M) a -= M;
  13.     return a;
  14. }
  15.  
  16. inline ll submod(ll a, ll b) {
  17.     a -= b;
  18.     if (a < 0) a += M;
  19.     return a;
  20. }
  21.  
  22. inline ll mulmod(ll a, ll b) {
  23.     return (a * b) % M;
  24. }
  25.  
  26. int n, p, q, S;
  27. vector<int> a;
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(0); cin.tie(0);
  31.  
  32.     // freopen(TASK".INP", "r", stdin);
  33.     // freopen(TASK".OUT", "w", stdout);
  34.  
  35.     cin >> n >> p >> q;
  36.     S = p + q;
  37.  
  38.     a.resize(n);
  39.     for (int i = 0; i < n; i++) {
  40.         int x, y;
  41.         cin >> x >> y;
  42.         a[i] = x + y;
  43.     }
  44.  
  45.     int L = 0;
  46.     for (int x : a) L += x;
  47.  
  48.     vector<ll> C(L + 1, 0), D(L + 1, 0), base(L + 1, 0), coef(L, 0);
  49.     D[0] = base[0] = 1;
  50.  
  51.     for (int i = 0; i < n; i++) {
  52.         vector<ll> E(L + 1, 0);
  53.         for (int s = 0; s <= L; s++) {
  54.             E[s] = addmod(E[s], D[s]);
  55.             if (s + a[i] <= L)
  56.                 E[s + a[i]] = submod(E[s + a[i]], D[s]);
  57.         }
  58.         D.swap(E);
  59.     }
  60.  
  61.     C = D;
  62.     for (int k = 1; k <= L; k++) {
  63.         coef[k - 1] = (M - (C[k] % M)) % M;
  64.     }
  65.  
  66.     for (int i = 0; i < n; i++)
  67.         for (int s = a[i]; s <= L; s++)
  68.             base[s] = addmod(base[s], base[s - a[i]]);
  69.  
  70.     if (S < L) {
  71.         cout << base[S] % M << "\n";
  72.         return 0;
  73.     }
  74.  
  75.     auto combine = [&](const vector<ll>& A, const vector<ll>& B) {
  76.         vector<ll> res(2 * L, 0);
  77.         for (int i = 0; i < L; i++) if (A[i]) {
  78.             for (int j = 0; j < L; j++) if (B[j]) {
  79.                 res[i + j] = addmod(res[i + j], mulmod(A[i], B[j]));
  80.             }
  81.         }
  82.         for (int i = (int)res.size() - 1; i >= L; i--) if (res[i]) {
  83.             for (int k = 1; k <= L; k++) {
  84.                 res[i - k] = addmod(res[i - k], mulmod(res[i], coef[k - 1]));
  85.             }
  86.         }
  87.         res.resize(L);
  88.         return res;
  89.     };
  90.  
  91.     function<vector<ll>(ll)> kitamasa = [&](ll n) -> vector<ll> {
  92.         if (n < L) {
  93.             vector<ll> pol(L, 0);
  94.             pol[(int)n] = 1;
  95.             return pol;
  96.         }
  97.         vector<ll> ans(L, 0); ans[0] = 1;
  98.         vector<ll> poly(L, 0); poly[1 % L] = 1;
  99.  
  100.         ll m = n;
  101.         while (m) {
  102.             if (m & 1LL) ans = combine(ans, poly);
  103.             poly = combine(poly, poly);
  104.             m >>= 1LL;
  105.         }
  106.         return ans;
  107.     };
  108.  
  109.     vector<ll> poly = kitamasa(S);
  110.     ll res = 0;
  111.     for (int i = 0; i < L; i++)
  112.         if (poly[i]) res = addmod(res, mulmod(poly[i], base[i]));
  113.  
  114.     cout << res % M << "\n";
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
10 1000000000 1000000000
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1
stdout 
575000001
https://ideone.com/TqGLiU
language:
C++14 (gcc 8.3)
created:
18 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!