Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- public class oc141019D {
- static int cur = 0, a, b;
- static int nextRand() {
- cur = cur * a + b;
- return cur >>> 16;
- }
- static void conv(int[] f, int sign) {
- for (int bit = 1; bit < f.length; bit *= 2) {
- int mask = f.length - bit - 1;
- for (int i = mask; ; i = (i - 1) & mask) {
- f[i | bit] += sign * f[i];
- if (i == 0) {
- break;
- }
- }
- }
- }
- public static void solve(Input in, PrintWriter out) throws IOException {
- int n = in.nextInt();
- int tests = in.nextInt();
- a = in.nextInt();
- b = in.nextInt();
- for (int test = 0; test < tests; ++test) {
- int[] f = new int[1 << n];
- for (int i = 0; i < 1 << n; ++i) {
- f[i] = nextRand();
- }
- int[] g = new int[1 << n];
- for (int i = 0; i < 1 << n; ++i) {
- g[i] = nextRand();
- }
- conv(f, 1);
- conv(g, 1);
- for (int i = 0; i < 1 << n; ++i) {
- f[i] *= g[i];
- }
- conv(f, -1);
- int ans = 0;
- for (int i = 0; i < 1 << n; ++i) {
- ans += f[i] * (i + 1);
- }
- out.println((long)(ans) & ((1L << 32) - 1));
- }
- }
- public static void main(String[] args) throws IOException {
- PrintWriter out = new PrintWriter("convolution.out");
- solve(new Input(new BufferedReader(new FileReader("convolution.in"))), out);
- out.close();
- }
- static class Input {
- BufferedReader in;
- StringBuilder sb = new StringBuilder();
- public Input(BufferedReader in) {
- this.in = in;
- }
- public Input(String s) {
- this.in = new BufferedReader(new StringReader(s));
- }
- public String next() throws IOException {
- sb.setLength(0);
- while (true) {
- int c = in.read();
- if (c == -1) {
- return null;
- }
- if (" \n\r\t".indexOf(c) == -1) {
- sb.append((char)c);
- break;
- }
- }
- while (true) {
- int c = in.read();
- if (c == -1 || " \n\r\t".indexOf(c) != -1) {
- break;
- }
- sb.append((char)c);
- }
- return sb.toString();
- }
- public int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- public long nextLong() throws IOException {
- return Long.parseLong(next());
- }
- public double nextDouble() throws IOException {
- return Double.parseDouble(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement