SHARE
TWEET

Untitled

a guest Dec 8th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.math.BigInteger;
  2. import java.util.StringTokenizer;
  3. import java.io.BufferedReader;
  4. import java.io.BufferedOutputStream;
  5. import java.io.IOException;
  6. import java.io.InputStream;
  7. import java.io.InputStreamReader;
  8. import java.io.PrintWriter;
  9. import java.io.OutputStream;
  10.  
  11. public class Alien {
  12.  
  13.     static final int MOD=1<<20;
  14.  
  15.     static long powmod(long x, long y) {
  16.      long res = 1;      // Initialize result
  17.  
  18.      x = x % MOD;  // Update x if it is more than or  
  19.      // equal to p
  20.  
  21.      while (y > 0)
  22.          {
  23.           // If y is odd, multiply x with result
  24.           if ((y & 1) != 0)
  25.               res = (res*x) % MOD;
  26.  
  27.           // y must be even now
  28.           y = y>>1; // y = y/2
  29.           x = (x*x) % MOD;  
  30.          }
  31.      return res;
  32.  
  33.     }
  34.  
  35.     static long col_sum(int i, int X, long [] fi_tbl) {
  36.      long fi = fi_tbl[i];
  37.      long res=fi;
  38.      long prev = fi;
  39.      long add_this = fi_tbl[X-1];
  40.      
  41.      for(int ii = 0; ii <X-1; ++ii) {
  42.          prev = (prev * powmod(33, X) + add_this) % MOD;
  43.          res += prev; res %= MOD;
  44.      }
  45.      return res;    
  46.     }
  47.  
  48.     // 107005050|00005252- construct right, construct left, multiply
  49.     static BigInteger FastBigInt(String x) {
  50.      int size = x.length();
  51.      if (size <= 5) {
  52.          return new BigInteger(x);
  53.      }
  54.      int last_half = size/2;
  55.      int last_half_size = size - last_half;
  56.      BigInteger lo = FastBigInt(x.substring(last_half,
  57.                                 last_half + last_half_size)); // last half
  58.      BigInteger hi = FastBigInt(x.substring(0, last_half)); // first half
  59.      return lo.add(BigInteger.TEN.pow(last_half_size).multiply(hi));
  60.     }
  61.  
  62.     public static void main(String [] args) throws IOException{
  63.      Kattio io = new Kattio(System.in, System.out);
  64.      int K, X;
  65.      K = io.getInt(); X = io.getInt();
  66.      String msg = io.r.readLine();
  67.      //System.out.println(msg);
  68.  
  69.      
  70.  
  71.      // should be a bit more?
  72.      long[] fi_tbl = new long[X];
  73.      fi_tbl[0] = 1;
  74.      for (int i=1; i<X; i++) {
  75.          fi_tbl[i] = (33*fi_tbl[i-1] + 1) % MOD;
  76.      }
  77.  
  78.      long l0 = col_sum(0, X, fi_tbl);
  79.      long l1 = col_sum(1, X, fi_tbl);
  80.  
  81.      long abez = 1016801;
  82.      long B = ((l1 - l0) * abez) % MOD;
  83.      long A = l0 - B;
  84.  
  85.      long[] all_col_sums = new long[X];
  86.      for (int i=0; i<X; i++) {
  87.          //System.out.println(A + "  " +  B + " " + fi_tbl[i]);
  88.          all_col_sums[i] = (((A + B*fi_tbl[i]) % MOD) + MOD) % MOD;
  89.          //System.out.println(all_col_sums[i]);
  90.      }
  91.  
  92.      //System.out.println("did compute col sums");
  93.  
  94.      StringBuilder s=new StringBuilder();
  95.      for (long x: all_col_sums)
  96.          s.append(""+x);
  97.      // System.out.println("did build string");
  98.      //BigInteger b= new BigInteger(s.toString());
  99.      BigInteger b = FastBigInt(s.toString());
  100.  
  101.      //System.out.println("did build integer");
  102.      
  103.  
  104.      String base27Java = b.toString(27);
  105.      
  106.      //System.out.println("did convert to base");
  107.      
  108.      StringBuilder buildRes = new StringBuilder();
  109.      for (int i=0; i<msg.length(); i++) {
  110.          int x = msg.charAt(i);
  111.          x -= 'A';
  112.          if (x < 0) x = 26; // space
  113.          char y = base27Java.charAt(i);
  114.          int yy = y >= 'a' ? y-'a' + 10 : y-'0';
  115.          int res = (x+yy) % 27;
  116.          char c = (char)(res + 'A');
  117.          if (c > 'Z') c = ' ';
  118.          buildRes.append(c);
  119.      }
  120.      io.println(buildRes.toString());
  121.      io.close();
  122.      
  123.      //for (long x: all_col_sums)
  124.      
  125.     }
  126.  
  127. }
  128.  
  129. /** Simple yet moderately fast I/O routines.
  130.  *
  131.  * Example usage:
  132.  *
  133.  * Kattio io = new Kattio(System.in, System.out);
  134.  *
  135.  * while (io.hasMoreTokens()) {
  136.  *    int n = io.getInt();
  137.  *    double d = io.getDouble();
  138.  *    double ans = d*n;
  139.  *
  140.  *    io.println("Answer: " + ans);
  141.  * }
  142.  *
  143.  * io.close();
  144.  *
  145.  *
  146.  * Some notes:
  147.  *
  148.  * - When done, you should always do io.close() or io.flush() on the
  149.  *   Kattio-instance, otherwise, you may lose output.
  150.  *
  151.  * - The getInt(), getDouble(), and getLong() methods will throw an
  152.  *   exception if there is no more data in the input, so it is generally
  153.  *   a good idea to use hasMoreTokens() to check for end-of-file.
  154.  *
  155.  * @author: Kattis
  156.  */
  157.  
  158.  
  159. class Kattio extends PrintWriter {
  160.     public Kattio(InputStream i) {
  161.         super(new BufferedOutputStream(System.out));
  162.         r = new BufferedReader(new InputStreamReader(i));
  163.     }
  164.     public Kattio(InputStream i, OutputStream o) {
  165.         super(new BufferedOutputStream(o));
  166.         r = new BufferedReader(new InputStreamReader(i));
  167.     }
  168.  
  169.     public boolean hasMoreTokens() {
  170.         return peekToken() != null;
  171.     }
  172.  
  173.     public int getInt() {
  174.         return Integer.parseInt(nextToken());
  175.     }
  176.  
  177.     public double getDouble() {
  178.         return Double.parseDouble(nextToken());
  179.     }
  180.  
  181.     public long getLong() {
  182.         return Long.parseLong(nextToken());
  183.     }
  184.  
  185.     public String getWord() {
  186.         return nextToken();
  187.     }
  188.  
  189.  
  190.  
  191.     public BufferedReader r;
  192.     private String line;
  193.     private StringTokenizer st;
  194.     private String token;
  195.  
  196.     private String peekToken() {
  197.         if (token == null)
  198.             try {
  199.                 while (st == null || !st.hasMoreTokens()) {
  200.                     line = r.readLine();
  201.                     if (line == null) return null;
  202.                     st = new StringTokenizer(line);
  203.                 }
  204.                 token = st.nextToken();
  205.             } catch (IOException e) { }
  206.         return token;
  207.     }
  208.  
  209.     private String nextToken() {
  210.         String ans = peekToken();
  211.         token = null;
  212.         return ans;
  213.     }
  214. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top