Show all threads Hide all threads Show all messages Hide all messages | WA 5 | Felix_Mate | 1747. Kingdom Inspection | 30 May 2017 19:51 | 2 | WA 5 Felix_Mate 29 May 2017 13:00 Мне кажется, что моя формула верна. Пусть f(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём любые два соседние числа различны; g(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём существует только одна пара соседних равных чисел. Тогда f(n)=n*(2*n-2)*f(n-1)+n*g(n-1), g(n)=n*(2*n-1)*f(n-1)+n*g(n-1) => f(n)=g(n)-n*f(n-1) => g(n-1)=f(n-1)+(n-1)*f(n-2) => f(n)=n*((2*n-1)*f(n-1)+n*(n-1)*f(n-2)). f(1)=0, f(2)=2 (mod p). Ответ на задачу f(n-1) mod p. Хотелось бы увидеть ответы на следующие тесты: 5 10000000 6 10000000 7 10000000 Edited by author 29.05.2017 13:01 Я неправильно записал формулу-рассуждения верные. Ошибка в 3 выводе. Нужно так: => f(n)=n*(2*n-1)*f(n-1)+n*(n-1)*f(n-2). | Fast Calculations | 198808xc | 1747. Kingdom Inspection | 5 Oct 2012 19:30 | 2 | Many people could find the formula, due to the inclusion-exclusion principle, but also many people could not find a proper method to calculate the formula, especially under module p. In fact, you don't need to calculate the huge combination numbers, nor do you need to perform some complex operations such as integer factorization. All you need is to rewrite the formula, and make it easier for calculation under module p. The formulation from inclusion-exclusion principle is: R = SUM (i = 0 to n) : (-1) ^ n * [(n + i)! / 2 ^ i] * C(n, i) where C(N, i) is the combination number, which is also the most difficult part in the formula. The key to calculation is rewrite the whole term, not only the combination number: [(n + i)! / 2 ^ i] * C(n, i) = [(n + i)! / 2 ^ i] * [n! / i! / (n - i)!] = [(n + i)! * n!] / [2 ^ i * i! * (n - i)!] = [(n + i)! / (n - i)!] / 2 ^ i * [n! / i!] Now, please note that, [(n + i)! / (n - i)!] could be recursively calculated: we need only to multiple (n + i) and (n + 1 - i) to the previous calculation result. Fortunately, there must be an even number in every pair of (n + i) and (n + 1 - i). So the increasing power of 2 could be also recursively canceled. Finally, the term [n! / i!] is easily calculated. Therefore, we solved the problem without a DIVISION calculation, which is hard to perform under module p. Hope this will help. nice xD one problem is that not everyone got exactly that formula, but instead another version of it. the fact that in your version of the formula you can obtain f(n) recursively only by multiplying two terms by f(n-1) makes it much easier. of course from the formula that i found i can get to yours, but thats more subtle. | i've found the formula - how compute it by modulo? | Baurzhan | 1747. Kingdom Inspection | 30 Oct 2011 07:06 | 4 | answer = all - 1_pair_bad+ 2_pair_bad + ...+(-1)^i_pair_bad = (2*n-2)!/2^(n-1) -> //all permutations of set{2,2,3,3,n,n}, //1 is the capital thats why don't included in set + sum(i=1,n-1)(-1)^i* //calculate bad permutations [C(i,n-1)*(2*n-2-i)!]/2^(n-1-i) this formula has 2 disadvantages: 1)calculating each Bad(i) requires O(i) time - counting factorial and degree, so, counting all Bad permutations will be TL. 2) division prevents us simply take each summand by modulo - even if a/b -> integer -> a/b != (a%p)/(b%p) --- We can avoid first disadvantage - Bad(i) can be counted in O(1) using bad(i-1) but modulo taking problem are still here. P/S I now that integer fraction's modulo can be found with fast_exponention and euler_function (like #140 in acm.mipt.ru) but i think it's not necessary here, i want solve this problem in linear time without number theory/ May be some reccurence exists? Does anybody know? Simple linear reccurence without number theory exists. Formula easy may be found in literature. Problem in computing binomials C[n,k] % p when n,k~10^5 and p is not prime. I think that formula C[n,k]=C[n,k-1]*(n-k+1)/k may be used but in realization: n-k+1=p1^(a1)*p2^(a2)...*pm^(am) and so for k also. In other words we are working in prime basis. In final answer all ai>=0 (because C[n,k] is int) and we don't need in finding h^(-1) mod p for some h. TLE...? C(n,k) has a long sequnce of prime factors for all k(I thought that more short) for example C(50,22)=(2^4)(7^2)(23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1). If find way to work with part (23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1) more quickly would be all Ok. Edited by author 04.04.2011 10:10 if p1, p2, ..., pk are the prime factors of p, you can precompute the factorials of all numbers in the following form k = a * p1^e1 * ... pk^ek for each factorial, keep the value a mod p and the exponents. now, with gcd(a,p) = 1 you can use modular inverses and subtract exponents in order to obtain the correct value of C(n,k) modulo p. | please give me right answer for this testcases... | napst101r | 1747. Kingdom Inspection | 28 Jun 2010 04:41 | 2 | 1000 1000000007 100000 1000000007 thanks If this will help you somehow... 1000 1000000007 -> 161507394 100000 1000000007 -> 573507585 | Why for n=4 answer is 30? | bsu.mmf.team | 1747. Kingdom Inspection | 30 Jan 2010 02:03 | 3 | In my opinion, for n=4 the correct answer is 20 if I understood the condition of the problem correctly, i.e for n=3 there are exists 2 ways: 123231 and 132321. Please, explain me my mistake if I'm wrong. 12324341 12342341 12342431 12343241 12343421 12423431 12432341 12432431 12434231 12434321 13234241 13242341 13242431 13243241 13243421 13423241 13423421 13424231 13424321 13432421 14232341 14232431 14234231 14234321 14243231 14323241 14323421 14324231 14324321 14342321 Oh! Now I understood my mistake. Thank you! |
|
|