|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | AC with long double | Shen Yang | 1594. Сокровища ацтеков | 2 ноя 2018 19:23 | 7 | deleted
Edited by author 21.10.2017 21:07 Why not std:: complex?
I have not read the code very carefully, maybe miss something important Maybe not possible to made it long double? it involves with Chebyshev polynomial U(x) is Chebyshev polynomial
Um(i*An/2)= i*An*Um-1(i*An/2)-Um-2(i*An/2) i is unit imaginary number
An is a n*n matrix Aij==1 if and only if abs(i-j)==1.
sqrt(det(Um(i*An/2）) is the answer..
I use long double because I need to judge the sign of sqrt(ans^2)
Edited by author 21.10.2017 09:46 Delete the code please. Posting AC code here violates the rules. You can explain your idea (which is not recommended either) 100 100
exactly result:
211296849512315762188619578574048657110653043609449472144725843973442479614058285996396387014570402447830177110492225916018306620473309898122553032154580078102848452707439935767561964432764309438889871659414420572001206784720890894593722611533746574726650832697664485530063095995962974740556608440361525520881534009295321784945692404915331234788462418215336479515406547891566477310928856298254153861327506039317299734093964771367687300616477954739907701770903890588939771176356807995358624375906635501695115399580918628783125903772434369374398388373031207325810190683145008704318854255120274024753774893652675256050843161415941752800234892558301824773136514256893938068687029095739098286424428752900415743287209790876036884080292271611832363684077924978489349099638343563775430445274281910983984807471952213028600596500243377496299053827784481766322799764412944529657092342282080566012889979741375614523723377108743228485047911163027695369684514018557778209543315449702696764786683247792132799136211383970764610828007749277178715661259454260357449248458683734007683846942145977953891807183259007702385978401831386444472112720952063414073905105738447216839800171442748174691808886777635485410113868685679678838952355104065272999262338505349001538065924096 | | How to solve this problem? (+) | Al.Cash | 1594. Сокровища ацтеков | 25 мар 2013 03:38 | 13 | The number of ways to tile an MxN rectangle with 1x2 dominos is
2^(M*N/2) times the product of
{ cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4)
over all m,n in the range 0<m<M+1, 0<n<N+1.
I have found this formula in internet and I would like to
know is there a way to use it for solving this problem? There is a solution of this problem which doesn't use this formula. But it uses something related to the problem name :) Don't you mean Aztec Diamond? And how is it connected then? =) Your guess is correct. The connection, however, is quite unobvious. The answer can be calculated as number of perfect matching in corresponding planar graph using Kasteleyn theorem. But it uses determinant of matrix (nm/2)x(mn/2) (symmetric and with zeroes) and complex numbers, so now i don't know, can or cannot it to be applied to this problem.
Hm, maybe it gives the formula posted by Al.Cash :-))))
Edited by author 21.06.2009 20:59 Yes, it gives exactly this formula =) But you can't use it due to precision reasons. We need integral-numbers formula... Very interesting from theoretical and practical point of view to use Java.BigDecimal with 1000-10000 digits
and catch right answer. Connection with Aztec Diamond! Something interest, but only for (2n)x(2n) squares:
Consider the 2n-by-2n matrix View the MathML source with mi,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|less-than-or-equals, slant2n and mi,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When ngreater-or-equal, slanted4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square. Nice problem! Finally got accepted after trying for 2 hours.
best,
Josh Bao
Edited by author 25.06.2009 12:34 2zbao: I think this gave us no useful information!
Edited by author 25.06.2009 15:27 Your submissions looks like some binary search or other cheatings... Why you get different wrongs many times for tests 29,33,34,36,38,40,42?
P.S. Sorry, if I am wrong.
Edited by author 25.06.2009 19:39 Wolfram Mathematica 8 allows you to use this formula with trigonometry.
He is a genius! It's a wonderful package!!! :) |
|
|
|
