fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define endl '\n'
  4. #define se second
  5. #define int long long
  6. #define getName(x) #x
  7. #define vi std::vector<int>
  8. #define isz(v) (int) v.size()
  9. #define pii std::pair<int, int>
  10. #define all(v) v.begin(), v.end()
  11. #define loop cerr << "here" << endl;
  12. #define breakLoop if(TIME > 1) break;
  13. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  14. using namespace std;
  15. typedef long long ll;
  16.  
  17.  
  18. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  19. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  20.  
  21. ll add(ll x, ll y, ll p){return (x % p + y % p + p) % p;}
  22. ll mul(ll x, ll y, ll p){return (x % p * y % p + p) % p;}
  23.  
  24. struct info{
  25.     int curVal, k, p, v;
  26. }q[207];
  27. int pre[60002][202], t, v = 2, maxi[2000007];
  28. vi compress;
  29.  
  30. int getID(int val){
  31.     return lower_bound(all(compress), val) - compress.begin() + 1;
  32. }
  33. int get(int val, int p){
  34.     //digit.clear();
  35.     string s;
  36.     int pow10 = 1, res = 0, idxP = getID(p);
  37.     for(int i = 0; i <= log10(val); i++)
  38.         s += ((val / pow10) % 10) + '0', pow10 *= 10;
  39.     sort(all(s));
  40.  
  41.     pow10 = 1;
  42.     for(int i = 0; i < isz(s); i++){
  43.         int r = s[i] - '0';
  44.         res = add(res, mul(r, add(pre[i * v + v - 1][idxP], (i * v == 0) ? 0 : -pre[i * v - 1][idxP], p), p), p);
  45.         pow10 *= 10;
  46.     }
  47.     return res;
  48. }
  49.  
  50. signed main(){
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.     #define task "t"
  54.     if (fopen(task".inp", "r")){
  55.         freopen(task".inp", "r", stdin);
  56.         freopen(task".out", "w", stdout);
  57.     }
  58.  
  59.     cin >> t;
  60.     for(int i = 1; i <= t; i++){
  61.         int curVal, k, p;
  62.         cin >> curVal >> k >> v >> p;
  63.         q[i] = {curVal, k, p, v};
  64.         maximize(maxi[p], v);
  65.         compress.push_back(p);
  66.     } sort(all(compress)); compress.erase(unique(all(compress)), compress.end());
  67.  
  68.     for(int tc = 1; tc <= t; tc++){
  69.         //cin >> curVal >> k >> p;
  70.         //v = 2;
  71.         int curVal = q[tc].curVal, k = q[tc].k, p = q[tc].p;
  72.         v = q[tc].v;
  73.  
  74.         if(!pre[0][getID(p)]){
  75.             int idxP = getID(p);
  76.             pre[0][idxP] = 1;
  77.             int curPow = 1;
  78.             for(int i = 1; i <= 6 * maxi[p]; i++)
  79.                 curPow = mul(curPow, 10, p), pre[i][idxP] = add(curPow, pre[i - 1][idxP], p);
  80.         }
  81.  
  82.         unordered_map <int, int> mp;
  83.         int timer = 0;
  84.         while(!mp.count(curVal) and k){
  85.             mp[curVal] = timer++;
  86.             k--;
  87.             curVal = get(curVal, p);
  88.         }
  89.         if(!k){
  90.             cout << curVal << ' ';
  91.             continue;
  92.         }
  93.         int cycleLen = timer - mp[curVal];
  94.         k %= cycleLen;
  95.         while(k--)
  96.             curVal = get(curVal, p);
  97.         cout << curVal << ' ';
  98.  
  99.  
  100.     }
  101.  
  102.  
  103.  
  104. }
  105. /*
  106. idea: xử dụng vòng lặp
  107. cm đpt: xấp xỉ 5008
  108. gọi xi là số lượng số chữ số i, i: 0 -> 9
  109. => x0 + x1 + ... + x9 = 6
  110. => tính bằng chia kẹo: (6 + 10 - 1)C(10 - 1) = 5008, rất thấp
  111. ngoài ra còn có sol bin lift, f[val][2^k] là số hiện tại nếu nhảy 2^k bước và giá trị ban đầu là val
  112. */
  113.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0wDymD
language:
C++14 (gcc 8.3)
created:
1 day 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!