| ENG RUS | Timus Online Judge |
Обсуждение задачи 1560. Elementary Symmetric FunctionsDirichlet Why p is prime? [5] // Задача 1560. Elementary Symmetric Functions 23 сен 2007 18:02 Is it possible to use somehow that p is prime? My AC solution doesn't use this fact, but I'm wondering is there a simpler way to solve this task. Victor Barinov (TNU) What complexity of your solution? [4] // Задача 1560. Elementary Symmetric Functions 23 сен 2007 22:12 Dirichlet Re: What complexity of your solution? [3] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 02:51 Complexity is (M + N) * log N, where N is a size of the array and M is a number of queries Denis Koshman Re: What complexity of your solution? [2] // Задача 1560. Elementary Symmetric Functions 15 авг 2008 16:24 I needed primality of 'p' when I calculated S(K) from sums of powers for Ai. I needed to divide by 2, 6 or 24 in the end. Primality plays important role when you find inverse of these divisors modulo 'p'. Also the fact that S>1000 was also convenient fact because some multiplications would turn to zero for quite small p. luckysundog Re: What complexity of your solution? [1] // Задача 1560. Elementary Symmetric Functions 10 сен 2011 20:09 This problem is named "Elementary Symmetric Functions". There is formula (by Newton) that gives relation between elementary symmetric polynomials and "power sums" (that are symmetric too). Formula used division that can be done in general case only by prime modulo. But it can be solved without knowing any special about these polynomials. In this case solution doesn't need the primality of P. And then we have a data structure problem only, not number theoretical :) I used interval tree and memoization of sums on subsegments. And still the 4 seconds limitation is too large. upd: Fenwick tree is better ;) Edited by author 10.09.2011 23:40 Artyom Re: What complexity of your solution? // Задача 1560. Elementary Symmetric Functions 3 дек 2021 20:36 I understand how to solve the problem with combinatoric formula and 4 segment trees, can you please explain the second way? fantasy Hint? [9] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 17:27 Could you please give me some hints? All my submissions get the same answer "time limit exceeded". svr Re: Hint? [7] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 19:40 Cumulative Frequency Tables ntmquan Re: Hint? // Задача 1560. Elementary Symmetric Functions 24 сен 2007 21:15 Can you explain it more concretly?With me, "Cumulative Frequency Tables" looks strange. svr Re: Hint? [5] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 21:50 In my words: It is 2^n type structure of data with O(log) insert and O(log) interval-[left,right] query in additive on subsets in [0,MAX] data, easy to programming. Best explanatuion in http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html ntmquan Re: Hint? [4] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 22:35 Thanks Vedernikoff Sergey Re: Hint? [3] // Задача 1560. Elementary Symmetric Functions 25 сен 2007 18:09 I think it is more usual to use Fenwick trees svr Re: Hint? [2] // Задача 1560. Elementary Symmetric Functions 27 сен 2007 14:08 Now I confirmed Cumulative Frequency Tables and ideas of http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html practically having AC 1.37 not very bad because used iostream. Tables better than Fenwick trees because they used only arrays. For adopting the method I used formulas a[k]=f(t0,t1,t2,...,tk) where tk=sum of A[i]^k and is additive contrary to a[k]. During a long time had WA7 because forgotten that abs does't work in __int64 and we must build our own abs for __int64. After cosmetic modifications have 0,843 Ac ant 3-th. Edited by author 27.09.2007 14:24 Edited by author 27.09.2007 14:31 Edited by author 27.09.2007 14:51 Edited by author 27.09.2007 14:52 Vedernikoff Sergey Re: Hint? [1] // Задача 1560. Elementary Symmetric Functions 29 сен 2007 03:25 For using Fenwick trees you also need only array, and, moreover, only one array! Denis Koshman Re: Hint? // Задача 1560. Elementary Symmetric Functions 15 авг 2008 16:21 I used 4 interval trees. One having Ai, another having Ai^2, another Ai^3 and the last one Ai^4. This way you can compute Al^k + ... + Ar^k in log(N) for k=1..4. This info is enough to calculate S(L..R, K). Aditya Sheth Re: Hint? // Задача 1560. Elementary Symmetric Functions 18 июл 2020 16:50 It can be easily done using Segment tree. Try to store this s[0...4] for each node in segment tree. Now you can find a nice formula using convolution to merge two nodes. IgorKoval(from Pskov) WA 7 // Задача 1560. Elementary Symmetric Functions 25 апр 2012 01:07 if you get WA 7 be careful! This code get WA: mypow(sum1,4) - 6*sum2*sum1*sum1) + 8*sum3*sum1 + 3*sum2*sum2 - 6*sum4 But this code get AC: mypow(sum1,4) %p - (6*(sum2*sum1%p)*sum1) %p + 8*(sum3*sum1%p) %p + 3*sum2*sum2 %p - 6*sum4 %p =) nikonoff (ONPU) To Admins ! [1] // Задача 1560. Elementary Symmetric Functions 19 янв 2009 16:53 There is mistake in test 16. We have: left == right && K == 4 but should be: K <= right - left + 1 Sandro (USU) Re: To Admins ! // Задача 1560. Elementary Symmetric Functions 20 янв 2009 11:45 Incorrect test 16 was fixed. All wrong verdicts are rejudged. svr How find 24^(-1) mod p [5] // Задача 1560. Elementary Symmetric Functions 22 сен 2007 22:32 One method uses formula a4=(t1^4-6*t1^2*t2+3*t2^2+8*t1*t3-6*t4)/24 mod p For it we must find previously 24^(-1) mod p But it needs in loop with ~ p=10^9 iterations May this calculation lead to TL before main program? Vedernikoff Sergey Re: How find 24^(-1) mod p // Задача 1560. Elementary Symmetric Functions 22 сен 2007 22:38 Why can't we use extended euclid? Ardian KP Re: How find 24^(-1) mod p // Задача 1560. Elementary Symmetric Functions 23 сен 2007 14:10 or use fermat little theorem a^(p-1) = 1 (mod p) a^(p-2).a = 1 (mod p) so a^(-1) = a^(p-2) :) Walrus (Dmitry Bochkarev) Re: How find 24^(-1) mod p [2] // Задача 1560. Elementary Symmetric Functions 30 сен 2007 01:03 // O(a) inline int inv(int a) { for (int i = 1; ; i++) { int64 b = (int64) P * i + 1; if (b % a == 0) return int(b / a); } return 0; } svr Re: How find 24^(-1) mod p [1] // Задача 1560. Elementary Symmetric Functions 30 сен 2007 09:39 Best advise was extended evclid I could apply it during the context. But 1560 wuild bettter to solve in Java using BigInt We simply use /24 at the end and avoid many %p operations. Denis Koshman Re: How find 24^(-1) mod p // Задача 1560. Elementary Symmetric Functions 15 авг 2008 16:16 a/b mod p = a*b^-1 mod p = a*b^(-1 mod p-1) mod p = a*b^(p-2) mod p. b^(p-2) can be precomputed using logarithmic powering. I needed only divisors 2, 6 and 24. UdSU: Abizyaev, Bikov, Urbanovich S(0) [1] // Задача 1560. Elementary Symmetric Functions 4 окт 2007 16:17 Does S(0) always equal 1? svr Re: S(0) // Задача 1560. Elementary Symmetric Functions 4 окт 2007 18:13 S(0) contains one set (I0,...,Ik)of indexes and it is empty. Product over empty set of indexes is 1, because products have multiplicative property with respect to union of disjoint index sets. Samsonov Ivan (Rybinsk SAAT) Please help [1] // Задача 1560. Elementary Symmetric Functions 22 сен 2007 18:25 "You should compute their values modulo prime P." (-1235+1+1+1+1+1)%1237=-1230, but answer 7. I do not understand =( Vedernikoff Sergey Re: Please help // Задача 1560. Elementary Symmetric Functions 22 сен 2007 18:38 According to famous mathematical convention we can write a % b = (n*b + a) % b as n tends to infinity. So, -1230 % 1237 is equivalent to (-1230 + 1237) % 1237 == 7
|