fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = (int)1e4 + 50, K = 1005, mod = (int)1e9 + 7;
  5.  
  6. int n, m;
  7. int a[N], b[N];
  8. int f[N][K], g[N][K];
  9.  
  10. inline void inc(int &a, int b) {
  11.     a += b;
  12.     if(a >= mod) a -= mod;
  13. }
  14.  
  15. void add(int *dp, int x) {
  16.     for(int i = 0; i + x < K; i++) inc(dp[i + x], dp[i]);
  17. }
  18.  
  19. void del(int *dp, int x) {
  20.     for(int i = K - 1; i >= x; i--) inc(dp[i], mod - dp[i - x]);
  21. }
  22.  
  23. int main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(NULL);
  26.  
  27.     int T;
  28.     cin >> T;
  29.     for(int cas = 1; cas <= T; cas++) {
  30.         cin >> n >> m;
  31.         for(int i = 1; i <= n; i++) {
  32.             cin >> a[i] >> b[i];
  33.             a[i] = (a[i] + 1) * b[i];
  34.         }
  35.         for(int j = 0; j < K; j++) {
  36.             f[0][j] = (j == 0);
  37.             g[0][j] = (j == 0);
  38.         }
  39.         for(int i = 1; i <= n; i++) {
  40.             memcpy(f[i], f[i-1], sizeof(f[i]));
  41.             add(f[i], b[i]);
  42.             del(f[i], a[i]);
  43.             memcpy(g[i], g[i-1], sizeof(g[i]));
  44.             add(g[i], a[i]);
  45.             del(g[i], b[i]);
  46.         }
  47.         for(int i = 1; i <= n; i++) {
  48.             for(int j = 1; j < K; j++) inc(f[i][j], f[i][j-1]);
  49.         }
  50.  
  51.         cout << "Case #" << cas << ":\n";
  52.         int ans = 0;
  53.         for(int i = 0; i < m; i++) {
  54.             int l, r, c; cin >> l >> r >> c;
  55.             l = (l + ans) % n + 1;
  56.             r = (r + ans) % n + 1;
  57.             if(l > r) swap(l, r);
  58.             ans = 0;
  59.             for(int j = 0; j <= c; j++) inc(ans, (int)(1LL * f[r][j] * g[l-1][c-j] % mod));
  60.             cout << ans << '\n';
  61.         }
  62.     }
  63. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1:
Case #2:
https://ideone.com/SfBx7q
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!