fork download
copy 
  1. #include <bits/stdc++.h>
  2. const int mod = 1e9+7;
  3. long long fp(long long b, int e){
  4.     if(e) return fp(b*b%mod, e>>1) * (e&1?b:1) % mod;
  5.     return 1;
  6. }
  7. long long solve_brute_force(int n, int x){
  8.     long long p = 1, ans{};
  9.     // before
  10.     for(int y=x; y; --y){
  11.         ans = (ans + y * fp(p, mod-2) % mod) % mod;
  12.         p = p * 3 % mod;
  13.     }
  14.     p = 1;
  15.     // after
  16.     for(int y =x; y <=n; ++y){
  17.         ans = (ans + y * fp(p, mod-2) % mod) % mod;
  18.         p = p * 3 % mod;
  19.     }
  20.     ans = ans * fp(3, mod-2) % mod;
  21.     return ans;
  22. }
  23. long long arithmetic_geometric_series(long long r, int n){
  24.     long long first_term = r * (1 + mod - fp(r, n)) % mod;
  25.     first_term = first_term * fp(fp((1+mod-r)%mod, 2), mod-2) % mod;
  26.     long long second_term = n * fp(r, n+1) % mod;
  27.     second_term = second_term * fp((1+mod-r)%mod, mod-2) % mod;
  28.     return (first_term + mod - second_term) % mod;
  29. }
  30. long long geometric_series(long long a, long long r, int n){
  31.     return ((a * fp(r, n+1) - a + mod) % mod) * fp(r-1, mod-2) % mod;
  32. }
  33. long long solve_optimized(int n, int x){
  34.     long long ans{};
  35.     // b
  36.     ans = (ans + arithmetic_geometric_series(3, x) * fp(fp(3, x), mod-2) % mod) % mod;
  37.     // after
  38.     ans = (ans + arithmetic_geometric_series(fp(3, mod-2), n-x)) % mod;
  39.     ans = (ans + geometric_series(x, fp(3, mod-2), n-x)) % mod;
  40.     ans = ans * fp(3, mod-2) % mod;
  41.     return ans;
  42. }
  43. signed main() {
  44.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  45.     int t;
  46.     std::cin >> t;
  47.     while(t--){
  48.         int n, q;
  49.         long long ans{};
  50.         std::cin >> n >> q;
  51.         while(q--){
  52.             int x;
  53.             std::cin >> x;
  54.             ans = (ans + solve_optimized(n, x)) % mod;
  55.         }
  56.         std::cout << ans << '\n';
  57.     }
  58. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
1
3 1
2
stdout
copy 
777777785
https://ideone.com/Sa6jFP
language:
C++14 (gcc 8.3)
created:
14 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!