I didn't realize the answer is when x is not a perfect square and otherwise. I solved it by calculating the answer for each individual prime power :

Let the number be p₁^α₁·p₂^α₂...·p_k^α_k. Now, consider an individual prime p_i. What is it's power in the final answer? It's p_i^{(1 + 2 + ... + α_i)(α₁ + 1)(α₂ + 1)...(α_i - 1 + 1)(α_i + 1 + 1)...(α_k + 1)}. We need to find this value for every prime divisor of the number and multiply them together.

Firstly, . Thus, we can calculate the sum in O(1). Note that in order to calculate , then it is enough to take x as its remainder when divided by 10⁹ + 6. Indeed, it is well-known that 10⁹ + 7 is a prime. Then, by Fermat's Little Theorem, , since p_i is not divisible by 10⁹ + 7. Thus, we need to first find the exponent of the expression modulo 10⁹ + 6.

We can easily reduce . However, how do we calculate (α₁ + 1)(α₂ + 1)...(α_i - 1 + 1)(α_i + 1 + 1)...(α_k + 1)} fast? Let P = (α₁ + 1)(α₂ + 1)...(α_i - 1 + 1)(α_i + 1)(α_i + 1 + 1)...(α_k + 1)}. This number is independent of i, so we can calculate it (mod 10⁹ + 6) in O(k). However, the product we want is P·(α_i + 1)^- 1. How do we calculate the inverse of a number modulo a number? First, we do it for when the modulus is prime. It is well-known that any number (1, 2, ..., p - 1) has a unique multiplicative inverse modulo p, for some prime p. Now, by Fermat's Little Theorem, x^- 1 ≡ x^p - 2 mod p, so we can find x^- 1 by calculating x^p - 2 (in O(logp) using exponentation by squaring). Now, sadly, 10⁹ + 6 isn't a prime. . Miraclously, is a prime, so we can in fact compute P·(α_i + 1)^- 1 modulo . Now, we want the exponent modulo 10⁹ + 6. So, we need to figure out whether the product is even or odd. If at least 2 of the a_is are odd, then the product is clearly even. Similarly, if all a_is are even, the product is clearly even. If exactly one a_i is odd, then if we calculate the prime power for p_i, the product is odd, else it's even. Now, we can now use Chinese Remainder Theorem to find P·(α_i + 1)^- 1 modulo 10⁹ + 6. Combining with (1 + 2 + ... + α_i) finally gives us the exponent of p_i modulo 10⁹ + 6. Now, it remains to use Exponentation by Squaring to determine the desired prime power and multiply the prime powers for all prime factors of the number.

On problem B, in this statement: 3. The numbers of points from the beginning of the tail to the end should strictly increase.

With this statement, Do you want to say that the number that identifies each vertex must strictly increase? Or that the quantity of vertices should increase?

For me its ambiguous. Sorry for the bad english and thanks for the contest i had fun.

Did anyone manage to get AC with hashing? I got TLE on case 16 :(

is there anyone? Help me why my code wrong answer(after 20th). I think if there are 2, 2, 3, 3, 3

At first, I calculated total combination using given prime. Using above example, there is 2 and the count of 2 is three. and there is 3 and the count of 3 is four. So, the total is 3 x 4 = 12

When calculating the answer, each given prime can sue the total combination with division For example, I get the total combination 12 So when calculating 2, the number of 2 is three, therefore '2' can appear 12/3 = 4.

In this process, the result is below

(2x4) x (4x4) x (3x3) x (9x3) x (27x3)

ll prime[200100]; ll total = 1; ll mod = 1e9 + 7; ll ans = 1; int n;

ll power(ll a, ll b){ ll val = 1; while (b){ if (b & 1) b--, val *= a; a *= a; b >>= 1; a %= mod; val %= mod; } return val; } int main(){ //freopen("input.txt", "r", stdin); cin >> n;

for (int i = 0; i < n; i++){
    ll p; cin >> p;
    prime[p]++; //cocunt the number of prime 'p'
}
for (int i = 0; i <= 200000; i++){
    total *= (prime[i] + 1); //calculate the whole possible combination
    total %= mod;
}
for (ll i = 1; i <= 200000; i++){
    if (prime[i] != 0){
       // a/b (% p) = a * b^(p-2) % p
        ll val = i;
        ll pw = power(prime[i] + 1, (mod - 2)); //pw is b^(p-2)
       ll comb = (total * pw) % mod;
        for (ll c = 1; c <= prime[i]; c++){
            ll next = power(val, comb); 
            ans = (ans * next) % mod;
            val *= i;
            val %= mod;
        }
    }
}
cout << ans;
return 0;

}

I did a little more analysis on B(although the solution is almost same).

Create a directed graph with edges going from higher to lower number. Now the Graph cannot have cycles just because it will disprove the definition of the graph.

Now since the Graph is a DAG we can easily apply DP on graph to take out: f(x) — the longest chain ending at x now answer is maximum of f(x) * out_degree[x]

The acyclic states was kind of unclear to me which took me time to solve it..

My solution to problem C: http://codeforces.net/contest/615/submission/15266012

Let rs be string s reversed. We find the longest prefix of t that is present in s or in rs, then we remove the suffix from t and repeat until t is empty. If the size of the suffix at some point is zero, then the answer is -1. One way to find such suffix is to do a binary search and get the longest suffix that is present in either s or rs.

Time complexity: O(|s||t+s|log|t|)

Can anyone explain why in problem D answer is calculated as ans = binPow(ans, (cnt[i] + 1)) * binPow(fp, d) % MOD; instead of ans=ans* binPow(fp, d) % MOD;

Problem C: I didn't understand this line:

"Now we will make an array endPos, where endPos[i] is true when t[i, i + cur_len - 1] = s[i - cur_len + 1, i]. We will update this array, adding symbols t[i], t[i + 1], t[i + 2] and so on."

what is cur_len? How to find cur_len? "adding symbols t[i], ... so on." where are we adding what? and how to use endpos to get the final answer?

Please someone clarify it in details!

In problem B what if there was a shorter path with very high number of spines so when we multiply with number of spines the final result of the shorter path is bigger than the longest path?

Problem D and E were really cool problems :) Though I messed up D in contest time and couldn't check E then :( But I solved E in one try and D just after the contest :'( It could have been a really good contest for me :(

Is there anyone attempt to solve Problem C with hash? I tried this, I think the complexity is about O(n^2) after I use unordered_map in c++11. However, It still takes too much time and got TLE.

I find the longest common segment in string s in this way: calculate all n^2 segments(inverse order included) hash value and stored them in unordered_map. The key in unordered_map is hash value of some segment, the value is the segment id. My code is 15269449. Could anyone tell me why TLE happened? Thank you

hi in 615D — Multipliers solution

d = d * (cnt[i] + 1) % (MOD — 1); why add (MOD-1) not MOD

d(4) = 3 , divisors (1,2,4) d(6) = 4 , divisors (1,2,3,6) d(4*6)= 8 divisors (1,2,3,4,6,8,12,24)

d(4*6) not equal d(4)*d(6)

A simpler solution with less math for D:

We need to calculate $$$n^ {\frac{d}{2}} \bmod p$$$ where $$$d$$$ is the count of divisors of $$$n$$$ (this is actually still true even if $$$d$$$ is odd).

And as we all know, if $$$n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$$$ then $$$d = (a_1 + 1) \times (a_2 + 1) \times \ldots \ (a_k + 1)$$$.

If any of $$$a_i$$$ is odd then we can divide the first $$$a_i + 1$$$ by 2 and then calculate normally.

Else every $$$a_i$$$ is even, i.e. $$$n$$$ is a square number, and we can use this fact to remove the $$$/2$$$ from $$$d/2$$$. Let $$$n = x^2$$$, then $$$n^\frac{d}{2} \Leftrightarrow (x^2)^{\frac{d}{2}} \Leftrightarrow x^{2\times \frac{d}{2}} \Leftrightarrow x^d$$$.

My (not so clean) implementation: 161385006.