fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define pb emplace_back
  6. #define ii pair<int, int>
  7. #define MASK(i) (1LL << (i))
  8. #define BIT(x, i) (((x) >> (i)) & 1)
  9. #define sz(s) (int)((s).size())
  10. #define all(a) a.begin(), a.end()
  11. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
  12. #define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
  13. #define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
  14. #define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
  15. using namespace std;
  16.  
  17. template<typename T1, typename T2> bool ckmax(T1 &A, const T2 &B){if(A < B){A = B;return true;} return false;}
  18. template<typename T1, typename T2> bool ckmin(T1 &A, const T2 &B){if(A > B){A = B;return true;} return false;}
  19.  
  20. const int MOD = (int)1234567891; // 998244353
  21. const int N = 123 + 10, M = 18;
  22. const int INF = (int)2e9 + 11;
  23. const long long LINF = (long long)4e18 + 11;
  24.  
  25. /*
  26.      /\_/\
  27.     (= ._.)
  28.     / >?  \>$
  29. */
  30.  
  31. #define int long long
  32. int pref[N], suf[N];
  33. int F[N], IF[N];
  34. int f[N];
  35.  
  36. int Pow(int a, int b){
  37.     int res = 1;
  38.     for(; b > 0; b >>= 1, a = 1LL * a * a % MOD) if(b & 1) res = 1LL * res * a % MOD;
  39.     return res;
  40. }
  41.  
  42. int S(int k, long long m){
  43.     int n = k+1;
  44.     pref[0] = m;
  45.     FOR(i, 1, n) pref[i] = 1LL * pref[i-1] * (m-i) % MOD;
  46.     suf[n] = m-n;
  47.     F0Rd(i, n) suf[i] = 1LL * suf[i+1] * (m-i) % MOD;
  48.  
  49.     int res = 0, fi = 0;
  50.     for(int i = 0; i <= n; i++){
  51.         fi = (fi + Pow(i, k) * (i > 0)) % MOD;
  52. //        cout << i << ' ' << fi << ' ' << Pow(i, k) << '\n';
  53.         int num = 1LL * (i == 0 ? 1 : pref[i-1]) * (i == n ? 1 : suf[i+1]) % MOD;
  54.         int dem = 1LL * IF[i] * IF[n-i] % MOD;
  55.         if((n-i) & 1) num = (MOD - num) % MOD;
  56.         (res += (1LL * fi * num % MOD * dem % MOD + MOD) % MOD) %= MOD;
  57.         if(res < 0) res += MOD;
  58.     }
  59.     return res;
  60. }
  61.  
  62. int T(int k, long long m){
  63.     int res = 1LL * (m+1) * S(k, m) % MOD;
  64.     res = (res + (MOD - S(k+1, m)) % MOD) % MOD;
  65.     return res;
  66. }
  67.  
  68. // code chưa xử lí tràn số khi m > 2*10^9
  69. void sol(void){
  70.     int k, a, m, d; cin >> k >> a >> m >> d;
  71.     int n = k+3;
  72.     F[0] = 1;
  73.     FOR(i, 1, n) F[i] = 1LL * F[i-1] * i % MOD;
  74.     IF[n] = Pow(F[n], MOD-2);
  75.     F0Rd(i, n) IF[i] = 1LL * IF[i+1] * (i+1) % MOD;
  76.  
  77.     // fi
  78.     f[0] = T(k, a);
  79.     FOR(i, 1, n) f[i] = (f[i-1] + T(k, a+i*d)) % MOD;
  80.  
  81.     // pref, suf
  82.     pref[0] = m;
  83.     FOR(i, 1, n) pref[i] = 1LL * pref[i-1] * (m-i) % MOD;
  84.     suf[n] = m-n;
  85.     F0Rd(i, n) suf[i] = 1LL * suf[i+1] * (m-i) % MOD;
  86.  
  87.     // f(x)
  88.     int res = 0;
  89.     for(int i = 0; i <= n; i++){
  90.         int num = 1LL * (i == 0 ? 1 : pref[i-1]) * (i == n ? 1 : suf[i+1]) % MOD;
  91.         int dem = 1LL * IF[i] * IF[n-i] % MOD;
  92.         if((n-i) & 1) num = (MOD - num) % MOD;
  93.         (res += (1LL * f[i] * num % MOD * dem % MOD + MOD) % MOD) %= MOD;
  94.         if(res < 0) res += MOD;
  95.     }
  96.     cout << res << '\n';
  97. }
  98.  
  99. signed main(void){
  100.     #define TASK "nhap"
  101.     if(fopen(TASK".inp", "r")){
  102.         freopen(TASK".inp", "r", stdin);
  103.         freopen(TASK".out", "w", stdout);
  104.     }
  105.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  106.     int t = 1;
  107.     cin >> t;
  108.     while(t--) sol();
  109.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
  110. }
  111.  
  112.  
Success #stdin #stdout #stderr 0.01s 5320KB
comments (?)
stdin
copy 
5
7 1234567886 1234567881 2
50 1200000000 2000000000 7000000
123 1600000000 1500000000 2000000
0 2000000000 1999999999 1
20 1 2000000000 15000000
stdout
copy 
403602293
559995554
1016935314
350864571
640695815
stderr
copy 
Time elapsed: 6 ms
https://ideone.com/cVfj4s
language:
C++14 (gcc 8.3)
created:
7 hours 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!