Answer this problem: ZerooCool is a Problem Setter, and he loves to have circles in his…
- User
Answer this problem:
ZerooCool is a Problem Setter, and he loves to have circles in his problems, a few days ago he came up with yet another circle problem but he couldn't find a solution to it, ZerooCool needs to find a solution for this problem to add it to the upcoming SCPC (Which is running now I think) Can you help him find it?
You are given a ratio R multiplied by 107 which represents an arc of a circle (E.g R=5∗106 means half a circle), what is the expected number of points added randomly on the circumference of the circle before they can't fit in an arc of size R
.
Output the answer modulo 109+7 .
- Assistant
To solve this problem, we'll need to find the expected number of points added randomly on the circumference of the circle before they can't fit in an arc of size R. Let's define ( N = 10^7 ) (since R is given in terms of ( 10^7 )), and ( D = N - R ).
Our target is to compute the expected value, which is given by the formula:
[ \text{Expected Number of Points} = \left( \frac{N}{D} \right)^2 ]
But since we're asked to compute this modulo ( 10^9 + 7 ), we need to compute this expression under modulus.
First, we calculate ( N^2 \mod (10^9+7) ) and ( D^2 \mod (10^9+7) ).
[ \text{numerator} = N^2 \mod p \ \text{denominator} = D^2 \mod p ]
To compute the modular inverse of the denominator, we use Fermat's Little Theorem, which states that for a prime modulus ( p ):
[ \text{modular inverse of } D^2 = D^{p-2} \mod p ]
Combining these, the expected number of points modulo ( 10^9 + 7 ) is:
[ \text{Answer} = (\text{numerator} \times \text{modular inverse of denominator}) \mod p ]
Here's the implementation of the solution:
def compute_expected_points(R): p = 10**9 + 7 N = 10**7 D = N - R numerator = pow(N % p, 2, p) denominator = pow(D % p, 2, p) # Compute modular inverse of the denominator under modulus p inv_denominator = pow(denominator, p - 2, p) answer = (numerator * inv_denominator) % p return answer # Example usage: R = int(input()) print(compute_expected_points(R))By using this formula, we can compute the expected number of points modulo ( 10^9 + 7 ) for any given R.