Waterloo 2017 Winter E - Vera and Love Triangles

View as PDF

Submit solution

Points: 25
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
2017 Winter Waterloo Local ACM Contest, Problem E

Vera has N friends numbered from 0 to N-1. Being in Software Engineering, all her friends do not have enough spare time to engage in relationships. However, friends have crushes on each other.

If x is a non-negative integer, let g(x) be the number of ones in the binary representation of x.

Let f(i,j) = g((A \cdot B^{i \cdot N + j}) \mathbin{\%} M), where A,B,M are integer constants.

It is known that for any 2 friends i and j where i < j, if f(i,j) is even then i has a crush on j, otherwise j has a crush on i.

Vera thinks love triangles are very funny. A love triangle is a set of 3 friends i,j,k such that i has a crush on j, j has a crush on k and k has a crush on i.

Given integers N,M,A,B tell Vera how many love triangles exist among her friends. Two love triangles are different if they contain a different set of 3 friends.

Constraints

  • 3 \le N, M \le 200\,000
  • 0 < A,B < M
  • N,M,A,B are integers
  • M is prime

Input Specification

The input will be in the format:

N M A B

Output Specification

Output one line with the number of love triangles.

Sample Input 1

3 5 3 4

Sample Output 1

1

Explanation of Sample Output 1

Let a \to b denote that friend a has a crush on friend b.

We have f(0,1) = 1, f(0,2)=2, and f(1,2)=1. So 0 \to 2, 2 \to 1, and 1 \to 0, so there is one love triangle.

Sample Input 2

3 3 1 2

Sample Output 2

0

Explanation of Sample Output 2

We have 1 \to 0, 2 \to 0, and 2 \to 1, so there are zero love triangles.

Sample Input 3

1337 10007 1337 1337

Sample Output 3

99141170

Comments

There are no comments at the moment.