fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6. typedef unsigned long long ULL;
  7. typedef unsigned int uint;
  8. typedef unsigned short ushort;
  9. typedef pair<int, int> PII;
  10.  
  11. #define MAX_INT (int)0x7fffffff
  12. #define MIN_INT (int)0x80000000
  13. #define MAX_UINT (uint)0xffffffff
  14.  
  15. #define TTi template<typename T> inline
  16. TTi T SQR(T x) { return x * x; }
  17.  
  18. #define CONCAT3_NX(x, y, z) x ## y ## z
  19. #define CONCAT3(x, y, z) CONCAT3_NX(x, y, z)
  20. #define VAR(name) CONCAT3(__tmpvar__, name, __LINE__)
  21. #define TYPE(x) __typeof(x)
  22.  
  23. #define FOR(i, s, n)  for (TYPE(n) i=(s),   VAR(end)=(n);  i <  VAR(end);  i++)
  24. #define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s);  i >= VAR(end);  i--)
  25. #define FORN(i, n)    FOR(i, 0, n)
  26. #define RFORN(i, n)   RFOR(i, 0, n)
  27. #define FOREACH(i, v) for (auto& i: v)
  28.  
  29. #define SC() scanf("\n")
  30. #define SC1(fmt, a) scanf(fmt, &a)
  31. #define SC2(fmt, a, b) scanf(fmt, &a, &b)
  32. #define SC3(fmt, a, b, c) scanf(fmt, &a, &b, &c)
  33. #define SCi(a) scanf("%d", &a)
  34. #define SCii(a,b) scanf("%d%d", &a, &b)
  35. #define SCiii(a,b,c) scanf("%d%d%d", &a, &b, &c)
  36. #define fLL "%lld"
  37. #define SCl(a) scanf(fLL, &a)
  38. #define SCll(a,b) scanf(fLL fLL, &a, &b)
  39. #define SClll(a,b,c) scanf(fLL fLL fLL, &a, &b, &c)
  40. #define SCs(s, n) {scanf("%s", s); n = strlen(s);}
  41. #define SCc(s) scanf("%c", s)
  42.  
  43. #define MP make_pair
  44. #define PB push_back
  45. #define WHOLE(x) (x).begin(),(x).end()
  46. #define SZ(x) ((int)(x).size())
  47. #define POPST(stack) (stack).top();(stack).pop();
  48. #define POPQ(queue) (queue).front();(queue).pop();
  49. #define CONTAINS(v, x) (find(WHOLE(v), (x)) != v.end())
  50. #define SORT(v) (sort(WHOLE(v)))
  51.  
  52. #define LIMIT(x, lim) {if (x > lim) x = lim;}
  53. TTi T MIN(T x, T y) { return (x < y) ? x : y; }
  54. TTi T MAX(T x, T y) { return (x > y) ? x : y; }
  55. TTi T ABS(T x) { return (x > 0) ? x : -x; }
  56. TTi void UPDATE_MIN(T &x, T y) {if (y < x) {x = y;}}
  57. TTi void UPDATE_MAX(T &x, T y) {if (x < y) {x = y;}}
  58. TTi int ARGMAX(T cont) { return max_element(cont.begin(), cont.end()) - cont.begin(); }
  59. TTi int ARGMIN(T cont) { return min_element(cont.begin(), cont.end()) - cont.begin(); }
  60.  
  61. vector<string> split(const string& s, char c) {
  62.     vector<string> v; stringstream ss(s); string x;
  63.     while (getline(ss, x, c)) v.emplace_back(x); return move(v);
  64. }
  65. template<typename T, typename... Args>
  66. inline string arrStr(T arr, int n) {
  67.     stringstream s;
  68.     s << "[";
  69.     FORN(i, n - 1) s << arr[i] << ",";
  70.     s << arr[n - 1] << "]";
  71.     return s.str();
  72. }
  73.  
  74. // #ifndef ONLINE_JUDGE
  75. #ifdef JUDGE_LOCAL
  76.     #define EPR(args...)   if (DEBUG) {fprintf(stderr, args);}
  77.     #define EARR(arr, n)   if (DEBUG) {FORN(i, n) fprintf(stderr, "%d, ", arr[i]);}
  78.     #define EVEC(arr)      if (DEBUG) {FORN(i, arr.size()) fprintf(stderr, "%d, ", arr[i]);}
  79.     #define EVARS(args...) if (DEBUG) { __evars_begin(__LINE__); __evars(split(#args, ',').begin(), args);}
  80.  
  81.     inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
  82.     inline void __evars(vector<string>::iterator it) {cerr << endl;}
  83.  
  84.     TTi void __evars_out_var(vector<T> val) {
  85.         cerr << arrStr(val, val.size());
  86.     }
  87.     TTi void __evars_out_var(T* val) {
  88.         cerr << arrStr(val, 10);
  89.     }
  90.     TTi void __evars_out_var(T val) {
  91.         cerr << val;
  92.     }
  93.     template<typename T, typename... Args>
  94.     inline void __evars(vector<string>::iterator it, T a, Args... args) {
  95.         cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  96.         __evars_out_var(a);
  97.         cerr << "; ";
  98.         __evars(++it, args...);
  99.     }
  100. #else
  101.     #define EPR(args...) 1
  102.     #define EARR(args...) 1
  103.     #define EVEC(args...) 1
  104.     #define EVARS(args...) 1
  105. #endif
  106.  
  107. template<class T> inline string TOSTR(const T & x) { stringstream ss; ss << x; return ss.str(); }
  108. #define DIE(args...) {printf(args);exit(0);}
  109. #define PR(x) cout << (x) << endl
  110. #define PRF(x) cout << fixed << setprecision(10) << x << endl
  111.  
  112. inline int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
  113. inline LL gcd(LL a, LL b) { return a ? gcd(b % a, a) : b; }
  114. inline LL powmod(LL a, LL p, LL m) { LL r = 1; while (p) { if (p & 1) r = r*a%m; p>>=1; a=a*a%m; } return r; }
  115.  
  116. struct pairhash {
  117.     template <typename T, typename U>
  118.     std::size_t operator() (const std::pair<T, U> &x) const {
  119.         return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  120.     }
  121. };
  122.  
  123. template <typename K, typename V>
  124. V GetWithDef(const std::unordered_map <K,V> & m, const K & key, const V & defval ) {
  125.     auto it = m.find(key);
  126.     return (it == m.end()) ? defval : it->second;
  127. }
  128.  
  129. template <typename K, typename V>
  130. void SetDef(std::unordered_map <K,V> & m, const K & key, const V & defval ) {
  131.     auto it = m.find(key);
  132.     if (it == m.end()) m[key] = defval;
  133. }
  134.  
  135. const int MOD = 1000 * 1000 * 1000 + 7;
  136. const double PI = 3.1415926535897932384626433832795l;
  137.  
  138. inline void addto(int &a, int b) {
  139.     a += b;
  140.     if (a >= MOD) a -= MOD;
  141. }
  142. inline int add(int a, int b) {
  143.     a += b;
  144.     if (a >= MOD) a -= MOD;
  145.     return a;
  146. }
  147. inline void subto(int &a, int b) {
  148.     a -= b;
  149.     if (a < 0) a += MOD;
  150.     if (a >= MOD) a -= MOD;
  151. }
  152. inline int sub(int a, int b) {
  153.     a -= b;
  154.     if (a < 0) a += MOD;
  155.     if (a >= MOD) a -= MOD;
  156.     return a;
  157. }
  158. inline void multo(int &a, int b) {
  159.     a = (long long)a * b % MOD;
  160. }
  161. inline int mul(int a, int b) {
  162.     return (long long)a * b % MOD;
  163. }
  164. inline int mulmod(int a, int b, int mod) {
  165.     return (long long)a * b % mod;
  166. }
  167. inline int powmod(int a, int e, int mod) {
  168.     int x;
  169.     for(x = 1; e > 0; e >>= 1) {
  170.         if (e & 1)
  171.             x = mulmod(x, a, mod);
  172.         a = mulmod(a, a, mod);
  173.     }
  174.     return x;
  175. }
  176. inline int invmod(int a, int mod) {
  177.     return powmod(a, mod - 2, mod);
  178. }
  179. inline LL invmodLL(LL p){
  180.     LL q=p;
  181.     for(LL a=p*p;a!=1;a*=a) q*=a;
  182.     return q;
  183. }
  184.  
  185.  
  186.  
  187. // -----------------------------------------------------------------
  188. // CODE
  189. // -----------------------------------------------------------------
  190.  
  191. #define DEBUG 1
  192.  
  193. int A, B, C, D, E, F;
  194. int F2, F1, G2, G1;
  195.  
  196. int K = 5;
  197. int M[200000][5][5] = {
  198.     {{1, 0, 0, 0, 0},
  199.      {0, 1, 0, 0, 0},
  200.      {0, 0, 1, 0, 0},
  201.      {0, 0, 0, 1, 0},
  202.      {0, 0, 0, 0, 1}}
  203. };
  204. int mlast = 2;
  205. int MATRIX_ID = 0;
  206. int MATRIX_STEP = 1;
  207.  
  208. int matmul(int ia, int ib) {
  209.     int res = mlast++;
  210.     // assert(res < 10000000);
  211.     FORN(i, K) {
  212.         int *rowres = M[res][i];
  213.         int *rowa = M[ia][i];
  214.         FORN(j, K)
  215.             FORN(k, K)
  216.                 addto(rowres[j], mul(rowa[k], M[ib][k][j]));
  217.     }
  218.     return res;
  219. }
  220.  
  221. // int matpow(int ia, int p) {
  222. //     if (p == 1)
  223. //         return ia;
  224. //     if (p % 2)
  225. //         return matmul(ia, matpow(ia, p-1));
  226. //     int ix = matpow(ia, p/2);
  227. //     return matmul(ix, ix);
  228. // }
  229.  
  230. vector<int> pre1;
  231. vector<int> pre2;
  232.  
  233. inline int solve(int n) {
  234.     int H2 = add(mul(E, F2), mul(F, G2));
  235.     if (n == 0) {
  236.         return H2;
  237.     }
  238.     int T1 = add(H2, add(mul(E, F1), mul(F, G1)));
  239.     if (n == 1) {
  240.         return T1;
  241.     }
  242.     int e = n - 1;
  243.     int low = e & ((1 << 15) - 1);
  244.     int high = e >> 15;
  245.     // assert(low < pre1.size());
  246.     // assert(high < pre2.size());
  247.     // EVARS(e, high, low);
  248.  
  249.     int ires = matmul(pre1[low], pre2[high]);
  250.     int init[5] = {F2, F1, G2, G1, T1};
  251.     int ans = 0;
  252.     FORN(i, K) {
  253.         addto(ans, mul(init[i], M[ires][K - 1][i]));
  254.     }
  255.     mlast--;
  256.     FORN(i, K) FORN(j, K) M[mlast][i][j] = 0;
  257.     return ans;
  258. }
  259.  
  260.  
  261. int main() {
  262.     ios_base::sync_with_stdio(0);
  263.  
  264.     // SCiii(A, B, C);
  265.     scanf("%d %d %d", &A, &B, &C);
  266.     A %= MOD;
  267.     B %= MOD;
  268.     C %= MOD;
  269.     scanf("%d %d %d", &D, &E, &F);
  270.  
  271.     // SCiii(D, E, F);
  272.     D %= MOD;
  273.     E %= MOD;
  274.     F %= MOD;
  275.     scanf("%d %d ", &F2, &F1);
  276.     scanf("%d %d ", &G2, &G1);
  277.  
  278.     // SCii(F2, F1);
  279.     // SCii(G2, G1);
  280.     F1 %= MOD;
  281.     F2 %= MOD;
  282.     G1 %= MOD;
  283.     G2 %= MOD;
  284.  
  285.     int EA = mul(E, A);
  286.     int EB = mul(E, B);
  287.     int FD = mul(F, D);
  288.     int FC = mul(F, C);
  289.  
  290.     int step[5][5] = {
  291.     //  F-2 F-1 G-2 G-1 T-1
  292.        {0,  1,  0,  0,  0}, // F-1
  293.        {0,  A,  B,  0,  0}, // F-0
  294.        {0,  0,  0,  1,  0}, // G-1
  295.        {D,  0,  0,  C,  0}, // G-0
  296.       {FD, EA, EB, FC,  1}, // T-0
  297.     };
  298.     FORN(i, 5) {
  299.     FORN(j, 5) {
  300.         M[MATRIX_STEP][i][j] = step[i][j];
  301.     }}
  302.  
  303.     int cur = MATRIX_ID;
  304.     FORN(i, 1 << 15) {
  305.         pre1.PB(cur);
  306.         cur = matmul(cur, MATRIX_STEP);
  307.     }
  308.  
  309.     int largestep = cur;
  310.     cur = MATRIX_ID;
  311.     FORN(i, 1 << 15) {
  312.         pre2.PB(cur);
  313.         cur = matmul(cur, largestep);
  314.     }
  315.  
  316.     int Q;
  317.     SCi(Q);
  318.     FORN(i, Q) {
  319.         int n;
  320.         scanf("%d", &n);
  321.         // SCi(n);
  322.         // EVARS(n);
  323.         printf("%d\n", solve(n));
  324.         // PR(solve(n));
  325.         // EPR("\n");
  326.     }
  327.  
  328.  
  329.     return 0;
  330. }
  331.  
Success #stdin #stdout 0.21s 23072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/anJgcj
language:
C++14 (gcc 8.3)
created:
8 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!