• API
• FAQ
• Tools
• Archive
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;
4. import java.io.BufferedOutputStream;
5. import java.io.IOException;
6. import java.io.InputStream;
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;
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
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();
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));
163.     }
164.     public Kattio(InputStream i, OutputStream o) {
165.         super(new BufferedOutputStream(o));
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.
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()) {
201.                     if (line == null) return null;
202.                     st = new StringTokenizer(line);
203.                 }
204.                 token = st.nextToken();
205.             } catch (IOException e) { }
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.

Top