| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Why p is prime? | Dirichlet | 1560. Elementary Symmetric Functions | 3 дек 2021 20:36 | 6 |
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. Complexity is (M + N) * log N, where N is a size of the array and M is a number of queries 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. 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 I understand how to solve the problem with combinatoric formula and 4 segment trees, can you please explain the second way? |
| Hint? | fantasy | 1560. Elementary Symmetric Functions | 18 июл 2020 16:50 | 10 |
Hint? fantasy 24 сен 2007 17:27 Could you please give me some hints? All my submissions get the same answer "time limit exceeded". Cumulative Frequency Tables Can you explain it more concretly?With me, "Cumulative Frequency Tables" looks strange. Re: Hint? Vedernikoff Sergey 25 сен 2007 18:09 I think it is more usual to use Fenwick trees Now I confirmed Cumulative Frequency Tables and ideas of http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.htmlpractically 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:52Re: Hint? Vedernikoff Sergey 29 сен 2007 03:25 For using Fenwick trees you also need only array, and, moreover, only one array! 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). 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. |
| WA 7 | IgorKoval(from Pskov) | 1560. Elementary Symmetric Functions | 25 апр 2012 01:07 | 1 |
WA 7 IgorKoval(from Pskov) 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
=) |
| To Admins ! | nikonoff (ONPU) | 1560. Elementary Symmetric Functions | 20 янв 2009 11:45 | 2 |
There is mistake in test 16.
We have: left == right && K == 4
but should be: K <= right - left + 1 Incorrect test 16 was fixed. All wrong verdicts are rejudged. |
| How find 24^(-1) mod p | svr | 1560. Elementary Symmetric Functions | 15 авг 2008 16:16 | 6 |
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? Why can't we use extended euclid? or use fermat little theorem
a^(p-1) = 1 (mod p)
a^(p-2).a = 1 (mod p)
so a^(-1) = a^(p-2) :) // 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;
} 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. 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. |
| S(0) | UdSU: Abizyaev, Bikov, Urbanovich | 1560. Elementary Symmetric Functions | 4 окт 2007 18:13 | 2 |
S(0) UdSU: Abizyaev, Bikov, Urbanovich 4 окт 2007 16:17 Does S(0) always equal 1? 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. |
| Please help | Samsonov Ivan (Rybinsk SAAT) | 1560. Elementary Symmetric Functions | 22 сен 2007 18:38 | 2 |
Please help Samsonov Ivan (Rybinsk SAAT) 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 =( 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 |
