{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2025-12-14T01:33:56.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2025-12-14T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":42778,"title":"GJam March 2016 IOW: Polynesiaglot Medium","description":"This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is a subset of small set 2. The max Qraw is 2^50 (\u003c1.1259e15) for C[1,50], V[1,50], L[1,15].\r\nThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\r\nInput: [C V L] , C[1,50], V[1,50], 1\u003c=L\u003c=15\r\nOutput: [Q] max Qraw is 2^50 (\u003c1.1259e15); Q=mod(Qraw,1E9+7)\r\nExamples: [C V L] [Q]\r\n[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\nGoogle Code Jam 2016 Open Qualifier: April 8, 2016\r\nTheory: This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\r\nQ3    V          C\r\nQ2  V   C       V\r\nQ1 V   V       V\r\n\r\nThis medium challenge has eps(Qraw) \u003c0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.44px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: none solid rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 522.625px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407.5px 261.312px; transform-origin: 407.5px 261.312px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 21px; text-align: left; transform-origin: 384.5px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThis Challenge is derived from\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e. This is a subset of small set 2. The max Qraw is 2^50 (\u0026lt;1.1259e15) for C[1,50], V[1,50], L[1,15].\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 21px; text-align: left; transform-origin: 384.5px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eInput:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=15\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eOutput:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [Q] max Qraw is 2^50 (\u0026lt;1.1259e15); Q=mod(Qraw,1E9+7)\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eExamples:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [C V L] [Q]\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 40.875px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 20.4375px; transform-origin: 404.5px 20.4375px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eare {bbaa, aaab} \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eare {ab,eb,bb}\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"font-weight: 700; \"\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 84px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 42px; text-align: left; transform-origin: 384.5px 42px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eTheory:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 81.75px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 40.875px; transform-origin: 404.5px 40.875px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ3    \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e          \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eC\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ2  \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e   \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eC\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e       \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ1 \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e   \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e       \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 31.5px; text-align: left; transform-origin: 384.5px 31.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThis medium challenge has eps(Qraw) \u0026lt;0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function Q=Polyglot(m)\r\n% Q total words of length L using C consonants and V vowels\r\n% Q is modulo 1E9+7\r\n C=m(1); V=m(2);L=m(3); %\r\n Q=0;\r\n\r\nend","test_suite":"%%\r\ntic\r\nm=[2 8 15 ];\r\nv=Polyglot(m);\r\nvexp=[6938704 ];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 7 15 ];\r\nv=Polyglot(m);\r\nvexp=[853390015];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 2 ];\r\nv=Polyglot(m);\r\nvexp=[8];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 3 ];\r\nv=Polyglot(m);\r\nvexp=[24];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 15];\r\nv=Polyglot(m);\r\nvexp=[32342016 ];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 2];\r\nv=Polyglot(m);\r\nvexp=[12];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 3];\r\nv=Polyglot(m);\r\nvexp=[40];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 4];\r\nv=Polyglot(m);\r\nvexp=[176];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[44 2 15];\r\nv=Polyglot(m);\r\nvexp=[916593151];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[1 3 15];\r\nv=Polyglot(m);\r\nvexp=[397629405];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 3 15];\r\nv=Polyglot(m);\r\nvexp=[105078522];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 4 15];\r\nv=Polyglot(m);\r\nvexp=[133836675];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 8 15];\r\nv=Polyglot(m);\r\nvexp=[6938704];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 8 14];\r\nv=Polyglot(m);\r\nvexp=[624439943];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 2];\r\nv=Polyglot(m);\r\nvexp=[5000];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 3];\r\nv=Polyglot(m);\r\nvexp=[375000];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 7];\r\nv=Polyglot(m);\r\nvexp=[249885158];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[10 20 10];\r\nv=Polyglot(m);\r\nvexp=[998720967];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[5 10 13];\r\nv=Polyglot(m);\r\nvexp=[746816099];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[1 1 13 ];\r\nv=Polyglot(m);\r\nvexp=[377 ];\r\nassert(isequal(vexp,v))\r\n\r\n\r\ntoc\r\n","published":true,"deleted":false,"likes_count":10,"comments_count":2,"created_by":3097,"edited_by":7,"edited_at":"2023-07-14T16:27:46.000Z","deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2016-03-19T18:33:48.000Z","updated_at":"2025-05-06T02:18:33.000Z","published_at":"2016-03-19T20:24:10.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis Challenge is derived from\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. This is a subset of small set 2. The max Qraw is 2^50 (\u0026lt;1.1259e15) for C[1,50], V[1,50], L[1,15].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eInput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=15\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eOutput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [Q] max Qraw is 2^50 (\u0026lt;1.1259e15); Q=mod(Qraw,1E9+7)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eExamples:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] [Q]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eTheory:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Q3    V          C\\nQ2  V   C       V\\nQ1 V   V       V\\n]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis medium challenge has eps(Qraw) \u0026lt;0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"},{"id":42779,"title":"GJam March 2016 IOW: Polynesiaglot Large","description":"This Challenge is derived from \u003chttp://code.google.com/codejam/contest/8274486/dashboard#s=p2 GJam March 2016 Annual I/O for Polynesiaglot\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\r\n\r\nThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\r\n\r\n*Input:* [C V L] , C[1,50], V[1,50], 1\u003c=L\u003c=500\r\n\r\n*Output:* [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\r\n\r\n*Examples:* [C V L] [Q]\r\n\r\n  [1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n  [1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\n \r\n\r\n*\u003chttp://code.google.com/codejam Google Code Jam 2016 Open Qualifier: April 8, 2016\u003e*\r\n\r\n*Theory:* This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1).  There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\r\n\r\n  Q3    V          C\r\n  Q2  V   C       V\r\n  Q1 V   V       V\r\n\r\nOne method to succeed in this problem is to use the java capability of Matlab.\r\n\u003chttp://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow Cody Java Challenge\u003e. The primary reference sites are \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html Java Math\u003e, \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html Java BigDecimal\u003e, and \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html Java BigInteger\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\r\n\r\n","description_html":"\u003cp\u003eThis Challenge is derived from \u003ca href = \"http://code.google.com/codejam/contest/8274486/dashboard#s=p2\"\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/a\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\u003c/p\u003e\u003cp\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/p\u003e\u003cp\u003e\u003cb\u003eInput:\u003c/b\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=500\u003c/p\u003e\u003cp\u003e\u003cb\u003eOutput:\u003c/b\u003e [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\u003c/p\u003e\u003cp\u003e\u003cb\u003eExamples:\u003c/b\u003e [C V L] [Q]\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\n\u003c/pre\u003e\u003cp\u003e\u003cb\u003e\u003ca href = \"http://code.google.com/codejam\"\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/a\u003e\u003c/b\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003eTheory:\u003c/b\u003e This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1).  There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eQ3    V          C\r\nQ2  V   C       V\r\nQ1 V   V       V\r\n\u003c/pre\u003e\u003cp\u003eOne method to succeed in this problem is to use the java capability of Matlab. \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\"\u003eCody Java Challenge\u003c/a\u003e. The primary reference sites are \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\"\u003eJava Math\u003c/a\u003e, \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\"\u003eJava BigDecimal\u003c/a\u003e, and \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\"\u003eJava BigInteger\u003c/a\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\u003c/p\u003e","function_template":"function [T]=Polyglot(m)\r\n% T total words of length L using C consonants and V vowels\r\n% \r\n% import java.math.*\r\n% xBI=BigInteger(12)\r\n% zBI=xBI.add(yBI);\r\n% zBI=xBI.multiply(yBI);\r\n% mBI=xBI.mod(BigInteger('1000000007'));\r\n% z=str2num(zBI); % Convert JavaBigInteger to numeric\r\n \r\n\r\n import java.math.*\r\n\r\n C=BigInteger(m(1));  % BigInteger\r\n V=BigInteger(m(2));  % BigInteger\r\n L=m(3); % \r\n\r\n\r\n% Values above 255 get mod applied so use string input to BigInteger \r\n TJ=TJ.mod(BigInteger('1000000007'));\r\n% Convert BigInteger type to a numeric \r\n T=str2num(TJ);\r\n \r\n \r\nend","test_suite":"%%\r\ntic\r\n% T 0.7\r\nm=[1 1 4 ];\r\nv=Polyglot(m);\r\nvexp=[5 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.8\r\nm=[1 2 2 ];\r\nv=Polyglot(m);\r\nvexp=[6 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[671294715 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[474858966 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 104.4\r\nm=[1 1 500 ];\r\nv=Polyglot(m);\r\nvexp=[523068127 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.3\r\nm=[2 2 1 ];\r\nv=Polyglot(m);\r\nvexp=[2 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[356064865 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[50 41 1 ];\r\nv=Polyglot(m);\r\nvexp=[41 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[396751820 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[938256882 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[883121986 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[684068183 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.3\r\nm=[4 3 2 ];\r\nv=Polyglot(m);\r\nvexp=[21 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[15068072 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[483582780 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[357963597 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[722287557 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 40 497 ];\r\nv=Polyglot(m);\r\nvexp=[142264969 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[300845428 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[626241204 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 50 499 ];\r\nv=Polyglot(m);\r\nvexp=[244005114 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.1\r\nm=[40 4 3 ];\r\nv=Polyglot(m);\r\nvexp=[1344 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[43 42 1 ];\r\nv=Polyglot(m);\r\nvexp=[42 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[518096485 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[223782662 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[678295851 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 2.2\r\nm=[50 3 2 ];\r\nv=Polyglot(m);\r\nvexp=[159 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 2.3\r\nm=[48 4 2 ];\r\nv=Polyglot(m);\r\nvexp=[208 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 41 498 ];\r\nv=Polyglot(m);\r\nvexp=[583339519 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.3\r\nm=[3 43 2 ];\r\nv=Polyglot(m);\r\nvexp=[1978 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[707985113 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[254325944 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.0\r\nm=[2 1 1 ];\r\nv=Polyglot(m);\r\nvexp=[1 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 5 499 ];\r\nv=Polyglot(m);\r\nvexp=[167403707 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[687213242 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[43 46 1 ];\r\nv=Polyglot(m);\r\nvexp=[46 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 4 498 ];\r\nv=Polyglot(m);\r\nvexp=[127737869 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 47 498 ];\r\nv=Polyglot(m);\r\nvexp=[809685798 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[701760607 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[783408764 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[3 40 499 ];\r\nv=Polyglot(m);\r\nvexp=[158384704 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[198880135 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 44 497 ];\r\nv=Polyglot(m);\r\nvexp=[539871481 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[227201453 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[212311056 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 254.9\r\nm=[2 2 500 ];\r\nv=Polyglot(m);\r\nvexp=[667073398 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[556413734 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 5.3\r\nm=[46 40 3 ];\r\nv=Polyglot(m);\r\nvexp=[211200 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 4 499 ];\r\nv=Polyglot(m);\r\nvexp=[334760532 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[328797447 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[225964115 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[690707538 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[195330871 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[5 4 2 ];\r\nv=Polyglot(m);\r\nvexp=[36 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[188049811 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.0\r\nm=[1 1 1 ];\r\nv=Polyglot(m);\r\nvexp=[1 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 218.1\r\nm=[1 2 500 ];\r\nv=Polyglot(m);\r\nvexp=[696656237 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[922192442 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[763469125 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[328920270 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 150.3\r\nm=[2 1 500 ];\r\nv=Polyglot(m);\r\nvexp=[260322005 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.4\r\nm=[5 49 2 ];\r\nv=Polyglot(m);\r\nvexp=[2646 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[237431455 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[29203332 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[376005947 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[378681068 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[795014271 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[42 44 1 ];\r\nv=Polyglot(m);\r\nvexp=[44 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[506257932 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 4 497 ];\r\nv=Polyglot(m);\r\nvexp=[272829097 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[50 50 1 ];\r\nv=Polyglot(m);\r\nvexp=[50 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.7\r\nm=[50 50 2 ];\r\nv=Polyglot(m);\r\nvexp=[5000 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[607981550 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[267081842 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[612852205 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[652373815 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 5 497 ];\r\nv=Polyglot(m);\r\nvexp=[336290141 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[50517743 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[251353420 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[66724508 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[390526622 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[37814577 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[923599754 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[872350727 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[668567771 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 4 498 ];\r\nv=Polyglot(m);\r\nvexp=[111334900 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.6\r\nm=[43 45 2 ];\r\nv=Polyglot(m);\r\nvexp=[3960 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[4 5 2 ];\r\nv=Polyglot(m);\r\nvexp=[45 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[281852157 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[884129281 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[216141546 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[488528258 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.3\r\nm=[5 42 2 ];\r\nv=Polyglot(m);\r\nvexp=[1974 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[45 45 1 ];\r\nv=Polyglot(m);\r\nvexp=[45 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[190132182 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.3\r\nm=[1 2 1 ];\r\nv=Polyglot(m);\r\nvexp=[2 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.6\r\nm=[47 42 2 ];\r\nv=Polyglot(m);\r\nvexp=[3738 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[4 45 499 ];\r\nv=Polyglot(m);\r\nvexp=[999945335 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[53296911 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[3178118 ];\r\nassert(isequal(vexp,v))\r\n\r\n\r\n\r\ntoc\r\n\r\n%%\r\n% Stacy992 March 12, 2016\r\n% import java.util.*;\r\n% public class c {\r\n% \tpublic static long[][] memo;\r\n% \tpublic static long mod = 1000000007;\r\n% \tpublic static int c, v, l;\r\n% \tpublic static void main(String[] args){\r\n% \t\tScanner in = new Scanner(System.in);\r\n% \t\tint t = in.nextInt();\r\n% \t\tfor(int z = 1;z\u003c=t;z++){\r\n% \t\t\tc = in.nextInt();\r\n% \t\t\tv = in.nextInt();\r\n% \t\t\tl = in.nextInt();\r\n% \t\t\tmemo = new long[2][l];\r\n% \t\t\tfor(int i = 0;i\u003c2;i++){\r\n% \t\t\t\tArrays.fill(memo[i], -1);\r\n% \t\t\t}\r\n% \t\t\t\r\n% \t\t\tSystem.out.println(\"Case #\"+z+\": \"+go(0, 0));\r\n% \t\t}\r\n% \t}\r\n% \tpublic static long go(int flag, int pos){\r\n% \t\tif(pos == l){\r\n% \t\t\tif(flag == 1){\r\n% \t\t\t\treturn 0;\r\n% \t\t\t}\r\n% \t\t\treturn 1;\r\n% \t\t}\r\n% \t\t\r\n% \t\tif(memo[flag][pos] != -1){\r\n% \t\t\treturn memo[flag][pos];\r\n% \t\t}\r\n% \t\t\r\n% \t\tlong ans = 0;\r\n% \t\tans = (ans+(go(0, pos+1)*v))%mod;\r\n% \t\tif(flag != 1){\r\n% \t\t\tans = (ans+(go(1, pos+1)*c))%mod;\r\n% \t\t}\r\n% \t\treturn memo[flag][pos] = ans;\r\n% \t}\r\n% }\r\n\r\n\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":3097,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":7,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2016-03-19T20:50:33.000Z","updated_at":"2016-03-19T23:05:52.000Z","published_at":"2016-03-19T23:05:52.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis Challenge is derived from\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://code.google.com/codejam/contest/8274486/dashboard#s=p2\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eInput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=500\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eOutput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eExamples:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] [Q]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://code.google.com/codejam\\\"\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eTheory:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Q3    V          C\\nQ2  V   C       V\\nQ1 V   V       V]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOne method to succeed in this problem is to use the java capability of Matlab.\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eCody Java Challenge\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The primary reference sites are\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava Math\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava BigDecimal\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e, and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava BigInteger\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":42778,"title":"GJam March 2016 IOW: Polynesiaglot Medium","description":"This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is a subset of small set 2. The max Qraw is 2^50 (\u003c1.1259e15) for C[1,50], V[1,50], L[1,15].\r\nThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\r\nInput: [C V L] , C[1,50], V[1,50], 1\u003c=L\u003c=15\r\nOutput: [Q] max Qraw is 2^50 (\u003c1.1259e15); Q=mod(Qraw,1E9+7)\r\nExamples: [C V L] [Q]\r\n[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\nGoogle Code Jam 2016 Open Qualifier: April 8, 2016\r\nTheory: This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\r\nQ3    V          C\r\nQ2  V   C       V\r\nQ1 V   V       V\r\n\r\nThis medium challenge has eps(Qraw) \u003c0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.44px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: none solid rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 522.625px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407.5px 261.312px; transform-origin: 407.5px 261.312px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 21px; text-align: left; transform-origin: 384.5px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThis Challenge is derived from\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e. This is a subset of small set 2. The max Qraw is 2^50 (\u0026lt;1.1259e15) for C[1,50], V[1,50], L[1,15].\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 21px; text-align: left; transform-origin: 384.5px 21px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eInput:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=15\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eOutput:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [Q] max Qraw is 2^50 (\u0026lt;1.1259e15); Q=mod(Qraw,1E9+7)\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eExamples:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e [C V L] [Q]\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 40.875px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 20.4375px; transform-origin: 404.5px 20.4375px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eare {bbaa, aaab} \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eare {ab,eb,bb}\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 10.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"font-weight: 700; \"\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 84px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384.5px 42px; text-align: left; transform-origin: 384.5px 42px; white-space-collapse: preserve; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eTheory:\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003e This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 81.75px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 40.875px; transform-origin: 404.5px 40.875px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ3    \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e          \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eC\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ2  \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e   \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eC\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e       \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003eQ1 \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e   \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e       \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); text-decoration: none; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); \"\u003eV\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4375px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404.5px 10.2188px; text-wrap: nowrap; transform-origin: 404.5px 10.2188px; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 0px; tab-size: 4; transform-origin: 0px 0px; white-space-collapse: preserve; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 31.5px; text-align: left; transform-origin: 384.5px 31.5px; white-space-collapse: preserve; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 0px; transform-origin: 0px 0px; \"\u003e\u003cspan style=\"\"\u003eThis medium challenge has eps(Qraw) \u0026lt;0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function Q=Polyglot(m)\r\n% Q total words of length L using C consonants and V vowels\r\n% Q is modulo 1E9+7\r\n C=m(1); V=m(2);L=m(3); %\r\n Q=0;\r\n\r\nend","test_suite":"%%\r\ntic\r\nm=[2 8 15 ];\r\nv=Polyglot(m);\r\nvexp=[6938704 ];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 7 15 ];\r\nv=Polyglot(m);\r\nvexp=[853390015];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 2 ];\r\nv=Polyglot(m);\r\nvexp=[8];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 3 ];\r\nv=Polyglot(m);\r\nvexp=[24];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 2 15];\r\nv=Polyglot(m);\r\nvexp=[32342016 ];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 2];\r\nv=Polyglot(m);\r\nvexp=[12];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 3];\r\nv=Polyglot(m);\r\nvexp=[40];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[4 2 4];\r\nv=Polyglot(m);\r\nvexp=[176];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[44 2 15];\r\nv=Polyglot(m);\r\nvexp=[916593151];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[1 3 15];\r\nv=Polyglot(m);\r\nvexp=[397629405];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 3 15];\r\nv=Polyglot(m);\r\nvexp=[105078522];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 4 15];\r\nv=Polyglot(m);\r\nvexp=[133836675];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 8 15];\r\nv=Polyglot(m);\r\nvexp=[6938704];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[2 8 14];\r\nv=Polyglot(m);\r\nvexp=[624439943];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 2];\r\nv=Polyglot(m);\r\nvexp=[5000];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 3];\r\nv=Polyglot(m);\r\nvexp=[375000];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[50 50 7];\r\nv=Polyglot(m);\r\nvexp=[249885158];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[10 20 10];\r\nv=Polyglot(m);\r\nvexp=[998720967];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[5 10 13];\r\nv=Polyglot(m);\r\nvexp=[746816099];\r\nassert(isequal(vexp,v))\r\n%%\r\nm=[1 1 13 ];\r\nv=Polyglot(m);\r\nvexp=[377 ];\r\nassert(isequal(vexp,v))\r\n\r\n\r\ntoc\r\n","published":true,"deleted":false,"likes_count":10,"comments_count":2,"created_by":3097,"edited_by":7,"edited_at":"2023-07-14T16:27:46.000Z","deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2016-03-19T18:33:48.000Z","updated_at":"2025-05-06T02:18:33.000Z","published_at":"2016-03-19T20:24:10.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis Challenge is derived from\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. This is a subset of small set 2. The max Qraw is 2^50 (\u0026lt;1.1259e15) for C[1,50], V[1,50], L[1,15].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eInput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=15\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eOutput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [Q] max Qraw is 2^50 (\u0026lt;1.1259e15); Q=mod(Qraw,1E9+7)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eExamples:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] [Q]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eTheory:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Q3    V          C\\nQ2  V   C       V\\nQ1 V   V       V\\n]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis medium challenge has eps(Qraw) \u0026lt;0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"},{"id":42779,"title":"GJam March 2016 IOW: Polynesiaglot Large","description":"This Challenge is derived from \u003chttp://code.google.com/codejam/contest/8274486/dashboard#s=p2 GJam March 2016 Annual I/O for Polynesiaglot\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\r\n\r\nThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\r\n\r\n*Input:* [C V L] , C[1,50], V[1,50], 1\u003c=L\u003c=500\r\n\r\n*Output:* [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\r\n\r\n*Examples:* [C V L] [Q]\r\n\r\n  [1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n  [1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\n \r\n\r\n*\u003chttp://code.google.com/codejam Google Code Jam 2016 Open Qualifier: April 8, 2016\u003e*\r\n\r\n*Theory:* This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1).  There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\r\n\r\n  Q3    V          C\r\n  Q2  V   C       V\r\n  Q1 V   V       V\r\n\r\nOne method to succeed in this problem is to use the java capability of Matlab.\r\n\u003chttp://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow Cody Java Challenge\u003e. The primary reference sites are \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html Java Math\u003e, \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html Java BigDecimal\u003e, and \u003chttp://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html Java BigInteger\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\r\n\r\n","description_html":"\u003cp\u003eThis Challenge is derived from \u003ca href = \"http://code.google.com/codejam/contest/8274486/dashboard#s=p2\"\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/a\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\u003c/p\u003e\u003cp\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/p\u003e\u003cp\u003e\u003cb\u003eInput:\u003c/b\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=500\u003c/p\u003e\u003cp\u003e\u003cb\u003eOutput:\u003c/b\u003e [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\u003c/p\u003e\u003cp\u003e\u003cb\u003eExamples:\u003c/b\u003e [C V L] [Q]\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \r\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}\r\n\u003c/pre\u003e\u003cp\u003e\u003cb\u003e\u003ca href = \"http://code.google.com/codejam\"\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/a\u003e\u003c/b\u003e\u003c/p\u003e\u003cp\u003e\u003cb\u003eTheory:\u003c/b\u003e This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1).  There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eQ3    V          C\r\nQ2  V   C       V\r\nQ1 V   V       V\r\n\u003c/pre\u003e\u003cp\u003eOne method to succeed in this problem is to use the java capability of Matlab. \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\"\u003eCody Java Challenge\u003c/a\u003e. The primary reference sites are \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\"\u003eJava Math\u003c/a\u003e, \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\"\u003eJava BigDecimal\u003c/a\u003e, and \u003ca href = \"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\"\u003eJava BigInteger\u003c/a\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\u003c/p\u003e","function_template":"function [T]=Polyglot(m)\r\n% T total words of length L using C consonants and V vowels\r\n% \r\n% import java.math.*\r\n% xBI=BigInteger(12)\r\n% zBI=xBI.add(yBI);\r\n% zBI=xBI.multiply(yBI);\r\n% mBI=xBI.mod(BigInteger('1000000007'));\r\n% z=str2num(zBI); % Convert JavaBigInteger to numeric\r\n \r\n\r\n import java.math.*\r\n\r\n C=BigInteger(m(1));  % BigInteger\r\n V=BigInteger(m(2));  % BigInteger\r\n L=m(3); % \r\n\r\n\r\n% Values above 255 get mod applied so use string input to BigInteger \r\n TJ=TJ.mod(BigInteger('1000000007'));\r\n% Convert BigInteger type to a numeric \r\n T=str2num(TJ);\r\n \r\n \r\nend","test_suite":"%%\r\ntic\r\n% T 0.7\r\nm=[1 1 4 ];\r\nv=Polyglot(m);\r\nvexp=[5 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.8\r\nm=[1 2 2 ];\r\nv=Polyglot(m);\r\nvexp=[6 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[671294715 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[474858966 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 104.4\r\nm=[1 1 500 ];\r\nv=Polyglot(m);\r\nvexp=[523068127 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.3\r\nm=[2 2 1 ];\r\nv=Polyglot(m);\r\nvexp=[2 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[356064865 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[50 41 1 ];\r\nv=Polyglot(m);\r\nvexp=[41 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[396751820 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[938256882 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[883121986 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[684068183 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.3\r\nm=[4 3 2 ];\r\nv=Polyglot(m);\r\nvexp=[21 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[15068072 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[483582780 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[357963597 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[722287557 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 40 497 ];\r\nv=Polyglot(m);\r\nvexp=[142264969 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[300845428 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[626241204 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 50 499 ];\r\nv=Polyglot(m);\r\nvexp=[244005114 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.1\r\nm=[40 4 3 ];\r\nv=Polyglot(m);\r\nvexp=[1344 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[43 42 1 ];\r\nv=Polyglot(m);\r\nvexp=[42 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[518096485 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[223782662 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[678295851 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 2.2\r\nm=[50 3 2 ];\r\nv=Polyglot(m);\r\nvexp=[159 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 2.3\r\nm=[48 4 2 ];\r\nv=Polyglot(m);\r\nvexp=[208 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 41 498 ];\r\nv=Polyglot(m);\r\nvexp=[583339519 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.3\r\nm=[3 43 2 ];\r\nv=Polyglot(m);\r\nvexp=[1978 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[707985113 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[254325944 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.0\r\nm=[2 1 1 ];\r\nv=Polyglot(m);\r\nvexp=[1 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 5 499 ];\r\nv=Polyglot(m);\r\nvexp=[167403707 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[687213242 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[43 46 1 ];\r\nv=Polyglot(m);\r\nvexp=[46 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 4 498 ];\r\nv=Polyglot(m);\r\nvexp=[127737869 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 47 498 ];\r\nv=Polyglot(m);\r\nvexp=[809685798 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[701760607 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[783408764 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[3 40 499 ];\r\nv=Polyglot(m);\r\nvexp=[158384704 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[198880135 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 44 497 ];\r\nv=Polyglot(m);\r\nvexp=[539871481 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[227201453 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[212311056 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 254.9\r\nm=[2 2 500 ];\r\nv=Polyglot(m);\r\nvexp=[667073398 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[556413734 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 5.3\r\nm=[46 40 3 ];\r\nv=Polyglot(m);\r\nvexp=[211200 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 4 499 ];\r\nv=Polyglot(m);\r\nvexp=[334760532 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 43 500 ];\r\nv=Polyglot(m);\r\nvexp=[328797447 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[225964115 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[690707538 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[195330871 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[5 4 2 ];\r\nv=Polyglot(m);\r\nvexp=[36 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[188049811 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.0\r\nm=[1 1 1 ];\r\nv=Polyglot(m);\r\nvexp=[1 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 218.1\r\nm=[1 2 500 ];\r\nv=Polyglot(m);\r\nvexp=[696656237 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[42 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[922192442 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[49 45 500 ];\r\nv=Polyglot(m);\r\nvexp=[763469125 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[328920270 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 150.3\r\nm=[2 1 500 ];\r\nv=Polyglot(m);\r\nvexp=[260322005 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.4\r\nm=[5 49 2 ];\r\nv=Polyglot(m);\r\nvexp=[2646 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[237431455 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[29203332 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[376005947 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[378681068 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[795014271 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.6\r\nm=[42 44 1 ];\r\nv=Polyglot(m);\r\nvexp=[44 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 41 500 ];\r\nv=Polyglot(m);\r\nvexp=[506257932 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 4 497 ];\r\nv=Polyglot(m);\r\nvexp=[272829097 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[50 50 1 ];\r\nv=Polyglot(m);\r\nvexp=[50 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.7\r\nm=[50 50 2 ];\r\nv=Polyglot(m);\r\nvexp=[5000 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[607981550 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[267081842 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[48 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[612852205 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[652373815 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[5 5 497 ];\r\nv=Polyglot(m);\r\nvexp=[336290141 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[50517743 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 46 500 ];\r\nv=Polyglot(m);\r\nvexp=[251353420 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[66724508 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 44 500 ];\r\nv=Polyglot(m);\r\nvexp=[390526622 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[45 47 500 ];\r\nv=Polyglot(m);\r\nvexp=[37814577 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[47 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[923599754 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[872350727 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[668567771 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 4 498 ];\r\nv=Polyglot(m);\r\nvexp=[111334900 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.6\r\nm=[43 45 2 ];\r\nv=Polyglot(m);\r\nvexp=[3960 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[4 5 2 ];\r\nv=Polyglot(m);\r\nvexp=[45 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 49 500 ];\r\nv=Polyglot(m);\r\nvexp=[281852157 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[43 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[884129281 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[41 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[216141546 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[40 42 500 ];\r\nv=Polyglot(m);\r\nvexp=[488528258 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.3\r\nm=[5 42 2 ];\r\nv=Polyglot(m);\r\nvexp=[1974 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 1.7\r\nm=[45 45 1 ];\r\nv=Polyglot(m);\r\nvexp=[45 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[46 48 500 ];\r\nv=Polyglot(m);\r\nvexp=[190132182 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 0.3\r\nm=[1 2 1 ];\r\nv=Polyglot(m);\r\nvexp=[2 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T 3.6\r\nm=[47 42 2 ];\r\nv=Polyglot(m);\r\nvexp=[3738 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[4 45 499 ];\r\nv=Polyglot(m);\r\nvexp=[999945335 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[44 40 500 ];\r\nv=Polyglot(m);\r\nvexp=[53296911 ];\r\nassert(isequal(vexp,v))\r\n%%\r\n% T Inf\r\nm=[50 50 500 ];\r\nv=Polyglot(m);\r\nvexp=[3178118 ];\r\nassert(isequal(vexp,v))\r\n\r\n\r\n\r\ntoc\r\n\r\n%%\r\n% Stacy992 March 12, 2016\r\n% import java.util.*;\r\n% public class c {\r\n% \tpublic static long[][] memo;\r\n% \tpublic static long mod = 1000000007;\r\n% \tpublic static int c, v, l;\r\n% \tpublic static void main(String[] args){\r\n% \t\tScanner in = new Scanner(System.in);\r\n% \t\tint t = in.nextInt();\r\n% \t\tfor(int z = 1;z\u003c=t;z++){\r\n% \t\t\tc = in.nextInt();\r\n% \t\t\tv = in.nextInt();\r\n% \t\t\tl = in.nextInt();\r\n% \t\t\tmemo = new long[2][l];\r\n% \t\t\tfor(int i = 0;i\u003c2;i++){\r\n% \t\t\t\tArrays.fill(memo[i], -1);\r\n% \t\t\t}\r\n% \t\t\t\r\n% \t\t\tSystem.out.println(\"Case #\"+z+\": \"+go(0, 0));\r\n% \t\t}\r\n% \t}\r\n% \tpublic static long go(int flag, int pos){\r\n% \t\tif(pos == l){\r\n% \t\t\tif(flag == 1){\r\n% \t\t\t\treturn 0;\r\n% \t\t\t}\r\n% \t\t\treturn 1;\r\n% \t\t}\r\n% \t\t\r\n% \t\tif(memo[flag][pos] != -1){\r\n% \t\t\treturn memo[flag][pos];\r\n% \t\t}\r\n% \t\t\r\n% \t\tlong ans = 0;\r\n% \t\tans = (ans+(go(0, pos+1)*v))%mod;\r\n% \t\tif(flag != 1){\r\n% \t\t\tans = (ans+(go(1, pos+1)*c))%mod;\r\n% \t\t}\r\n% \t\treturn memo[flag][pos] = ans;\r\n% \t}\r\n% }\r\n\r\n\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":0,"created_by":3097,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":7,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2016-03-19T20:50:33.000Z","updated_at":"2016-03-19T23:05:52.000Z","published_at":"2016-03-19T23:05:52.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis Challenge is derived from\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://code.google.com/codejam/contest/8274486/dashboard#s=p2\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eGJam March 2016 Annual I/O for Polynesiaglot\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. This is the Large input set. The max Qraw is 100^500, (V+C)^L.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eInput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] , C[1,50], V[1,50], 1\u0026lt;=L\u0026lt;=500\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eOutput:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [Q] max Qraw is 100^500; Q=mod(Qraw,1E9+7)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eExamples:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e [C V L] [Q]\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba}  invalid are {bbaa, aaab} \\n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://code.google.com/codejam\\\"\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eGoogle Code Jam 2016 Open Qualifier: April 8, 2016\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eTheory:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e This is a huge value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(L-1)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Q3    V          C\\nQ2  V   C       V\\nQ1 V   V       V]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOne method to succeed in this problem is to use the java capability of Matlab.\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eCody Java Challenge\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The primary reference sites are\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava Math\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava BigDecimal\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e, and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eJava BigInteger\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The Java solution by the winner Stacy is included at the bottom of the test suite.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"term":"tag:\"probability tree\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"probability tree\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"probability tree\"","","\"","probability tree","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f19b8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1738\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007fa2d463fd20\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f1c38\u003e":1,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1b98\u003e":50,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1af8\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007fa2d45f1a58\u003e":"tag:\"probability tree\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f1a58\u003e":"tag:\"probability tree\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"search","password":"J3bGPZzQ7asjJcCk","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"probability tree\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"probability tree\"","","\"","probability tree","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f19b8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1738\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007fa2d463fd20\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f1c38\u003e":1,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1b98\u003e":50,"#\u003cMathWorks::Search::Field:0x00007fa2d45f1af8\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007fa2d45f1a58\u003e":"tag:\"probability tree\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007fa2d45f1a58\u003e":"tag:\"probability tree\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":42778,"difficulty_rating":"easy-medium"},{"id":42779,"difficulty_rating":"medium"}]}}