We'll use the "standard" LIS algorithm with binary searching: sweep through the array, and maintain an array of dp[l] = min(A[i] s.t. there's an increasing sequence of length l ending at A[i]).

When we see a new value A[k], we binary search and find the maximum length l such that dp[l] < A[k]; then we know there's an increasing sequence of length l+1 ending at A[k]. Also, l is maximal, so dp[l+1] > A[k], so we should update dp[l+1] = A[k].

Now, note that the sequence over time of values of dp[l] is decreasing. Thus, these are precisely a partition of the permutation into |LIS| decreasing subsequences, so we can store a vector for each dp[l], and get the subsequences.

If you calculate the expected value for a given n with k = 1 (one step), you see that the answer is simply σ₁(n) / σ₀(n), where σ₁(n) denotes the sum of divisors of n and σ₀(n) the number of divisors.

It's well known that σ₁ and σ₀ are multiplicative functions (and easy to prove indeed). So, it's easy to see from there using induction that the function is multiplicative.

I wasn't sure when I was in the contest, so I used DFS to search all the divisors of n, the complexity is correct.

E[f(X)g(Y)] = E[f(X)]×E[g(Y)], if X and Y are independent. Here exponents of each prime divisor of N are independent of each other, and E(.) denotes the expectation value.

Since the constrains are small, u can apply brute force, a simple approach is that for every given angle u can consider rotating it either clockwise(+) or anti-clockwise(-). Do it for all the angles in the array and keep summing them, if in one of the ways u get a final sum(after one complete traversal of array) which is divisible by 360, then output 'yes' other wise if non of the ways satisfy the condition sum%360==0 then output 'no'. There are total 2^15 ways(maximum) of obtaining the final sum. Refer to my solution for more clarity. https://mirror.codeforces.com/contest/1097/submission/47914337

sum ( dp(k -1,j + i) * (1 / (j + i + 1)) ), i goes from 0 to (p -j). Not sure though

https://mirror.codeforces.com/blog/entry/64310?#comment-482095

At most one means zero or one.

like this:47957456

it is O(nk) and can be O(nk / 32) if you use bitset

47954506

My idea is similar but not same with yours.

First we can use Stirling number to split power into several falling factorial，e.g

f(S)^k=sum{i=1...k}S(k,i)f(S)_(i)，where x_(i)=x(x-1)...(x-i+1)=C(x,i)i!

then we should compute sum C(f(S),i), for every 1<=i<=k.

this is equivalent to choose i egdes and sum the number of sets valid(that means f(X) includes these edges).

then we can DP with dp(i,j) means choose j edges in i's subtree, and each egde chosen has at least one node of its subtree in the vertex set. and then the answer is dp(1,i) minus unvalid ways, the latter is only possible when (j-1) edges are all in the other's subtree(and no vertex outside this subtree is in the set). you can enumerate the "highest" edge, and the ways of this can be easily gotten use dp values.

Same feeling...

Unfortunately, that's just not efficient enough. That solution gives you sequences, but you need around .

The key to the solution is that, if the LIS isn't long enough, we take the entire set of decreasing subsequences, not just the longest decreasing subsequence. Note that in general, repeatedly removing the longest/last decreasing subsequence doesn't give you the minimum cover: consider 3 0 4 2 1: you might want to take 3 2 1, but the only minimal cover is 3 0 and 4 2 1.

https://mirror.codeforces.com/blog/entry/64310?#comment-482095

Solve this: https://mirror.codeforces.com/problemset/problem/803/F

Inclusion-exclusion for the problem above explained: https://mirror.codeforces.com/blog/entry/51755?#comment-356983 the formula using mobius is in the editorial (it's the same thing)

,because any t can be 0 ~ t with equal probability after an operation. You can notice that , so you can calculate it in O(α k).

Actually I was a little afraid of having TLE even with correct solution. It was O(k log^2 n) with multiplications and modules. When I checked how long it takes on maxtest (2^something) it turned out it is quick, but it's not like k could have been increased significantly ... unless you would like to require binary exponentiation of matrices ;)

https://mirror.codeforces.com/blog/entry/64310?#comment-482095

If you have A[i] and B[i] multiples of i, there will be A[i] * B[i] multiples of i after taking gcd of all pairs. Also, multiplication mod 2 is &.

It's something about Stirling Numbers of the second kind. Where S(k,i) is the Stirling Number. And ... It become a DP problem. My code:https://mirror.codeforces.com/contest/1097/submission/48029930

How would you pair up the strings? I can guarantee that you only find 2 pairs, therefore the answer is 2.

Let me guess, Radewoosh is still enjoying the New Year, so he hasn't uploaded the editorial yet

which problem bro?

Clockwise means $$$+a_i$$$ and counterclockwise means $$$-a_i$$$. And you need to find a subset of clockwise moves $$$A_{cw} $$$ and counter-clock-wise moves $$$A_{ccw}$$$. To open the lock, it must satisfy $$$\sum_{a\in A_{cw}}a-\sum_{a\in A_{ccw}}a=360*k$$$ for an integer value of $$$k$$$. Rewrite the above formulation, you have $$$2\sum_{a\in A_{cw}}a-S=360*k$$$ where $$$S=a_1+...+a_n$$$. So generating subset sums of $$$2a_i$$$ (it is a classic DP problem) and check if any of them satisfies the above condition, or $$$2\sum_{a\in A_{cw}}a=S$$$ (mod 360).