Strawberry

SRM 762 · 2019-07-01 · by teja349

SRM 762 · 2019-07-01 · by teja349 · Dynamic Programming, Math

Show categories

Class Name: Strawberry

Return Type: int

Method Name: competitive

Arg Types: (int, int, vector<int>, vector<int>)

Problem Statement

Teja and Raja are experienced players in CSGo (Catch the Strawberry and go). CSGo is a two-player game consisting of n rounds. Teja and Raja play alternate rounds, Teja goes first. (Thus, Teja plays rounds 1, 3, 5, ..., while Raja plays rounds 2, 4, 6, ...)

At the beginning of the entire game Teja and Raja each have zero strawberries. In each round of CSGo, the active player can gain between 0 and 2*k strawberries. The actual number of strawberries gained is a random event (more details below) and all these random events are mutually independent.

You are given the int[]s A and B. For each valid index i, let pA(i) = A[i] / sum(A) and let pB(i) = B[i] / sum(B). The value pA(i) is the probability that Teja gains exactly i strawberries in any one round in which he is the active player. The value pB(i) is the same for Raja.

For spectators a game of CSGo is competitive if the absolute difference between the number of Teja's and the number of Raja's strawberries never exceeds k. (I.e., after each round the difference must be k or less.)

What is the probability with which the game between Teja and Raja will be competitive? It can be shown that the answer is always rational. Let X/Y be the answer in reduced form. Let Z = Y^(-1) be the inverse element to Y when computing modulo 10^9 + 7. Compute and return the value (X*Z) modulo 10^9 + 7.

Notes

The inverse element to Y when computing modulo 10^9 + 7 is the only Z in the range [0, 10^9 + 6] such that Y*Z = 1 (modulo 10^9 + 7).
You may assume that the answer is always well-defined: the probability is always a fraction X/Y such that Y has a unique inverse element.

Constraints

n will be between 1 and 100 inclusive.
k will be between 1 and 100 inclusive.
A and B will each contain exactly 2*k+1 elements.
Each element of A and B will be between 0 and 10^9+6 inclusive.
The sum of A will not be a multiple of 10^9+7.
The sum of B will not be a multiple of 10^9+7.

Examples

93
94
{173942897,55729246,750210935,595502724,350348365,592823762,458608170,776609607,323119032,864461632,165070684,666663579,429413850,333023455,112574938,347731663,557777257,738042994,693722695,2719749,605771991,18997856,749399130,401673939,74036497,438933225,358577447,530058107,803270320,34430037,523882664,929880014,242088164,143230750,697948459,207049279,466520880,558223175,783862665,806815771,666489889,696364740,465146765,405115507,938856081,112734229,487776589,641992937,819233701,901747810,546641883,374758559,300585567,535158246,590693446,190747630,384909074,109251910,635232134,257068012,104154975,415569231,779157254,344225015,237766507,801230930,203833175,778264398,894715915,291637259,823344262,150395447,609202957,329898585,464631001,49262862,845687681,635416409,426098733,433857275,644347826,319809695,327864703,530067695,199854302,255773760,297356910,622339043,642076151,870539705,915730076,590967687,878656138,524971841,278882060,133050745,745149412,637523040,341972559,411913209,378921911,640622952,729317555,185850611,357656169,378102175,605874302,12830617,463934327,116054463,597027297,727759045,715559460,839045875,580649244,55850006,865638857,31915634,774560485,45908871,60222101,533242219,424685930,309871012,631134556,864747367,611132340,364054686,111732513,356582513,672080192,232427764,335555867,957709682,340124444,581235568,792058264,857523148,271111060,136112775,247942478,242830789,234779451,957413578,303999888,93151839,313704174,975913056,537056351,857724047,631758051,514899396,24007389,861327739,467762210,983619972,494690712,73367747,901656616,643100798,126338601,467625875,938384393,781372265,924144063,379709907,421529312,297113493,557566374,648980051,330006808,204025155,713703072,871588612,844961568,953909301,774177994,484270762,940694463,147410464,120203445,978056997,803306521,764591367,932657562,968590348,32452512,87340316,961610932}
{244517388,539082635,940119719,238252597,414426282,83735537,543016877,493053949,679145355,891620896,587430590,132327304,957195317,43894524,293619003,362617675,347630186,566961558,100142228,659236937,606124483,711530949,554234989,356313025,586183291,5176493,28361751,380994623,21806217,629623227,397570812,757497487,43391477,54628732,397847046,205809485,53387255,505972343,757857601,133336687,787782754,83251176,800675049,860948548,228840200,252094529,637609667,500633680,320543279,273541758,310652143,184842142,200873468,403456424,704511324,326222272,481373890,923139298,139571539,529232468,153560063,658122435,439460866,37931817,428436953,988448475,510686639,120957679,629433730,43876327,173290457,741744834,782937469,617618894,451433290,702475417,909347012,840354330,89867946,724043763,293338722,731851544,162401344,591089544,27937591,778859924,730762271,219461430,467601899,872042267,496219135,662907022,798501034,981484510,508662595,263949555,295030263,580663357,186870552,227364258,739667479,760682991,996072531,141539668,284247507,154167574,738445482,92577828,984053199,415509323,816763209,312017883,968144946,34035014,279599775,476715901,96344671,266114267,158021138,41111324,838190917,287882546,120859110,728277822,345480514,831339773,970284217,789436075,542456744,845446508,728660980,127765705,273639471,22256006,344533659,473336836,542349623,739510584,205279316,896697177,656207984,352746516,159911437,300157397,601611518,498040915,432219973,845430250,856363332,78393893,787211163,444215043,564677801,430241790,860531926,142324135,627852263,498455499,527974888,840011709,124221781,369904388,806339001,54189200,536205176,699534123,194802048,200367226,539119111,355957630,628273128,564716258,271272197,237993311,855531156,317190673,498570903,13661182,378465538,162667935,82804420,633797488,77249878,306161466,86439914,769104487,769897383,586919935,781367049}
Returns: 301673145

91
95
{550314539,475160590,327327139,61824143,111046829,713632911,997547636,366434031,732801840,364200115,419681528,769693399,953810034,600178119,211481402,246183452,160613368,812985600,508387078,470050158,724351786,87278033,42933761,623445765,454229659,77535500,748686448,670274738,644883004,141895673,710152500,642585913,165502267,911816453,586292456,351540258,952520011,550634968,821642141,821571178,953802314,297392026,72412521,473316656,803146685,706921545,410422511,895645318,263708744,460703,728930036,255109446,905264330,764307077,287345434,711573195,425903248,962430209,273268434,185365262,472209296,835926503,962748858,257918790,519676135,656154818,609683158,434060461,892079139,200237523,534198012,228698597,396488490,678441343,280336217,539147919,732403416,41925789,11247649,823312418,249130206,527883043,550773755,94386328,580593740,928611798,115372754,224500458,262467847,14917367,472281638,763817637,388440716,796482008,29539281,573088200,357990292,479427017,876738884,107535721,831055175,215817144,636559029,477158891,599730509,507279153,139383153,446491004,208444248,514171517,55805586,406342105,112161382,361127948,946466218,899845171,823008386,76776104,776333795,328767378,891886574,1346824,482408011,496784953,121426907,576615594,263654736,284841244,948367248,182145899,868576537,15319242,233358038,321098910,691581517,911266522,185218760,835928382,579418089,761956204,165745189,876197149,96024520,893905044,528848066,860097289,629191320,396297480,622751619,94635723,622352680,186511988,209538300,297808594,810371253,676701297,860328195,563997817,962207408,844452816,613061309,574772802,831042731,583344034,834667858,550572728,688308719,923238197,442043092,953366814,558181580,757754269,96705254,639229833,827670973,221969527,391762902,449781555,605366841,15191436,986214453,666367049,870263423,466057292,698599849,310582737,192099564,156658489,946382258,783226882,590896327}
{16713430,860954399,489300502,412273419,69523814,75269798,610381809,963956338,574341718,704719350,877432893,413336142,323562628,881895243,437484006,909838887,41201007,927378070,580829176,189979853,441043996,560883262,26767216,445463455,822632869,550945134,169392943,374957368,132795232,43252167,919403339,574601845,532384855,910602366,474359678,111578292,235345800,875649649,429958121,473008003,539240029,462404734,276798447,515677980,532009699,728188600,46028491,646616289,608369097,203918763,123176233,153289436,119251208,533266490,547435810,659331470,908189415,160427321,732125404,518854601,351655735,788813597,581614083,337433753,878934933,964757533,973282285,892473079,511850202,1867017,720598161,793607952,708326398,80332575,499478716,812748295,319042968,147179418,520909667,620994267,731152680,754198921,281132618,85756023,330085532,345244744,483750308,378861373,300425533,679787455,401708476,41708533,23526785,646346877,770699562,461929637,328850401,794597502,871068493,2300677,527433478,52829642,131585136,369491724,201070888,436608640,504489971,862745044,310041142,264874333,620907560,989391323,145060533,100046669,895451974,149311033,164231176,140843635,332440410,162182377,428651949,69299942,880357977,236338609,207707396,696954109,292603996,653501669,614281115,136532414,88118477,478402665,478030886,974592155,34523267,307088051,320337464,640477810,760424879,4535531,839052865,73973149,133111969,348381084,803037917,824042535,481305753,747070232,804339,337640905,386993933,773313458,56596445,444300060,886366800,734867596,980276262,757188139,997296212,786360265,52895330,903359192,992402578,641094310,231409456,973722853,472217356,671554035,438764408,158974709,56517976,834759242,583479974,90405543,196700857,543591967,396265911,930039596,878235686,656291028,18758786,708398079,696286946,897356799,928021906,607226206,980053365,383484073,421297316,577438159,100546420}
Returns: 834658206

99
95
{109060775,553017286,616384029,703371393,253408869,84615516,415749130,392357159,270879544,651366604,816041006,557262912,947309039,937970859,258882008,25503913,199294727,127338624,567413273,962654268,789982790,798592689,92938528,697866661,282159472,624250984,710626819,524136132,850713786,412838184,236683628,994973826,476601417,401944135,698965347,417012174,282943935,842321378,349206629,676967991,491522588,456200030,624263805,258863897,553288812,61022731,100591798,468653449,943422612,735410794,123694570,428185626,216159367,30340405,994884045,384609645,188577511,296562709,13235938,504363102,527995189,277816321,748537709,499878319,414447065,697068961,498233172,526389018,254569969,65694405,912514260,312616449,551837469,317446818,489724954,579279686,95008235,297970774,965135432,982370284,135984761,281421994,983868979,349517119,733487080,255366445,859745160,674957369,0,216990785,140343545,927298578,230225662,613727313,601910164,398669073,951547927,739817252,652586204,467285263,801288568,303758153,60578511,157115309,304343071,323533478,783896550,402271259,134009560,778984606,981487200,632524847,307105633,681864236,618830730,627407534,220676228,66290876,129413198,477267796,522998656,592432915,847618678,868460332,866639787,235037912,113637404,7821906,567456725,294158194,553960902,577150484,420781967,434697347,391782450,641124804,595992522,65359735,363072654,0,432186207,398813475,694778799,530577767,870439704,100486577,46243111,609652980,27521757,112296863,822944714,875703370,439738051,460638720,572334433,995930702,611762143,813120,583920881,692375393,481214988,929680812,938079397,689239697,148628326,392054790,568674213,699735558,400768664,253304595,20259067,273822045,874191436,177656660,130408761,478984821,934167060,78691653,192794790,478122919,539229604,123259438,886705555,612002443,943956276,820379670,488660440,194035192,776614333,476139306,970816107}
{312382093,447873016,999767659,758005343,705541753,289514090,54581605,180946672,755363102,307262546,335124236,82266534,260883044,652916850,240337264,406507693,124999127,962034009,288973394,77460632,848625468,561885176,746224869,412497523,262746306,693861663,564233860,693403212,298712949,325519019,687929580,214961039,103068623,552503187,109325663,803208407,171120849,504263318,69898004,333114481,272610165,639086411,968239200,628679070,46307489,96215271,716336058,410132414,722856014,194954198,987770712,15959525,201558526,359871428,186517132,713317316,236314385,473612583,532538194,78511210,258277354,678899117,426962987,16696255,122313538,212326278,443130564,846861881,699663643,31063780,238944302,430650757,57576659,792007487,403519490,286795691,21900875,224081359,435450752,188397621,299301974,214468703,810302959,483437608,305782400,594539785,387724902,365021022,854474445,141439883,941335029,99852865,443948971,525849861,676331365,478406531,153803237,666511604,14258907,930497000,534470151,358948045,609326016,298082248,320754987,614828929,86775831,214297616,1721637,921135912,416835242,181598943,329210469,949355598,516201626,275010711,421034106,653665724,158915896,980744744,387367616,805701071,49360295,52782490,491298637,55541556,111623413,140923462,172595826,332486653,660971728,585176806,698805447,402544688,617477359,8081549,802913538,205175086,877674755,39344823,687378636,748817376,420828819,911718695,905187918,633473138,738122118,511756044,482738563,881178768,676398787,465618265,637923982,602029420,88919502,976987772,14050478,122363062,975841292,438828114,54179374,129974163,218821820,1027696,710926102,582391625,255825191,675450168,769283911,34382803,352053420,595953107,337261288,75279281,237373454,809437641,90457455,748285008,340308327,647225406,777429303,191323165,272342486,368568383,555736077,304991468,219378788,375441368,507989699,247018843,93124291}
Returns: 968432635

92
98
{530934066,886232704,853762360,945879137,4667126,989436150,930868500,65092476,604423280,199445361,946846843,282862532,136673391,797346887,473128460,147712409,124453810,147680908,942549546,166737834,323700752,221713704,954785223,0,282191931,934191830,49506049,820672493,453371326,988544620,962367066,121445969,252804459,763171723,219862186,146005422,282173290,629615896,815301644,601007303,994555579,351342466,174473714,157265113,432403412,717302891,584741337,589029080,397877462,559840286,482012529,319296589,693894450,0,359821293,997088386,144064916,431328923,348366892,91087964,786144749,268877439,992373891,753770490,14254880,19188005,53201379,134313457,688946604,83566718,233482456,638616208,99433530,512481777,156348057,491921116,524784811,138779147,820013439,598370740,85254816,412424350,456857041,439336491,136130334,820626284,301540423,42814442,184109207,63174018,944726088,632266792,497600244,638790050,366037953,843486707,894730471,304950826,628398296,197715597,432048708,163739524,279523830,668718411,372290093,154863379,888148999,816525852,585632342,298365981,442514884,894438027,991109535,350161495,588763402,301347953,186940644,127691379,366120562,409088077,521524340,577204475,785178104,71427918,878361007,818466752,304602294,53075209,409331774,581129232,723174086,967958755,755210268,512153390,311244957,455485952,950075774,127294175,638114573,391644885,541699286,447507830,704198976,816948055,800928689,638076380,953522009,888028407,69754918,186209797,612916734,701886051,96420798,85138163,109877841,493184120,717662093,680011218,678461277,94084569,219040775,869027418,154859679,566604171,545120037,378807083,807685600,857890610,872817280,299059722,845169052,20529977,796136751,731165682,652202904,443788590,529108930,83682954,807612523,364499047,775035657,174130350,791171071,369051536,717405216,489709927,0,537960606,996493671,761879870,853540483,656099958,508911224,801723037,674105292,194194131,213343991}
{873406307,817396636,674089477,467626865,623677772,410015295,689427773,798899923,470015848,357742437,487751338,403582741,970831045,699557064,270519720,638518546,183457537,310999403,141348827,849471025,543464436,223944010,923436835,229484782,0,587122134,444061077,509989826,833375489,82432639,756037775,773933510,540276855,411217680,276018911,624778719,660149534,885366782,292014526,324318145,287296807,207993799,779990145,260919925,839479818,122215379,395662217,5203152,653251858,936241161,229870380,380803320,11674830,108045097,537484709,346142918,322201153,207951622,408679898,895395337,489883537,822905515,262954886,723645393,271053335,471214942,130387944,133298982,623356517,119355297,341327581,797432796,272619597,817322792,775913056,962283011,39598410,538236120,499454431,921383084,919798559,928149642,377928405,860629558,849714306,113431709,326875334,152086235,587511940,928104685,294938946,717938332,8318530,218511203,143759067,660670736,123682234,510825499,215227121,440987374,279585209,601035659,384185630,400087840,252137587,251773395,799309284,347843084,808694449,306254451,761821441,297594859,777616858,970368475,315292391,104777647,32715641,876678115,504296136,246692062,795030110,219452963,312000905,823801685,548526873,721905500,139465538,182378273,712727523,843548754,991746938,317424489,762947981,44880544,598170882,842876994,786090653,801877073,946575167,0,952705890,10677552,402279708,515031527,988853710,537353205,974902230,534567524,731392484,276883947,930853821,438605663,780651941,149040538,424267509,433199374,410814582,469798261,328725550,132591805,222113621,839081650,703753084,976452780,465541939,967528638,777421693,794470024,270325589,807798218,925204463,135634636,835334460,132063190,496001106,421320211,686098502,629844228,776716478,413024994,513577626,135520242,688936070,566328575,129716264,767123007,690032624,622740011,800160957,97551412,157830485,516859505,794112082,51993749,486911120,897611905,787175164}
Returns: 199520048

100
91
{682129336,104967788,602250103,179103762,785067008,476226293,803910275,44418881,378027591,570750179,938465459,643664262,767922068,854825845,513616680,877585761,290420724,130017236,287211141,408498817,42743788,425179126,548486813,717712843,261930398,796224340,881002215,202676692,240936957,415551753,392153507,835618827,598981388,817781895,962416102,320933723,349199901,711644719,947309039,122547800,802084465,639601423,673461872,447015959,778360781,980320106,751867885,817761758,323394748,408415363,114192429,307186319,630950475,410920882,622937334,18502701,666432444,955729262,258218985,905344932,462087208,341755820,788567003,974413775,429201827,257976336,725507023,779332947,351914144,235611015,343577624,868390558,611598886,798858015,383191011,380477233,104440892,701753907,917442510,450906233,158189277,85686864,147816452,627319480,874131222,775438595,297287237,697252992,368424429,209655170,339001712,665833209,178511341,463141479,42477485,621754142,993693947,542479792,26239854,118627032,950544193,904766150,42790545,439460008,373360776,250773612,516678692,407561234,50255899,653600483,360513171,932984690,249076158,631058174,608058670,727314123,134599601,163111180,546866559,770552485,746693788,247290114,258336593,737931851,494734955,993862980,247897607,54033973,403956639,786032540,214859635,11215032,971364350,422826447,589590438,999531456,809040334,486047444,339965763,264368035,211623060,723277666,935210891,867075661,740083541,562409836,201845021,360756938,22630260,812676369,838395729,175019238,534849849,849412528,750667905,381939500,841903598,340512414,349919769,156712952,821452782,549786322,265753345,763078303,443061121,112552485,982682831,454712,877943628,292763002,918589293,192838004,521209268,497509102,451482858,713253652,299667280,626224287,136265494,763227875,973348713,111494672,219645261}
{98447027,958105300,134864070,100041397,851342528,148958336,620594908,33935990,310646065,844659818,3794351,916989802,358992281,597182206,353264553,569809269,349422660,657614899,718471856,758004743,30172787,498592987,857766124,992401251,722757625,722080107,680909506,125424440,148827225,781085941,295594239,955926004,624063662,808189922,500851695,618783130,988461829,274309050,19404963,622480375,4996263,394715928,720846025,850825804,571261162,455515314,377361193,13137210,431464055,971304898,954886108,870328037,734021754,718527498,577205680,242422851,695754732,685677642,115973187,782106341,730946280,215162465,885456669,185619214,32331813,912626227,543781164,323956278,878359946,962448890,752358416,763259722,389227709,445725633,183640195,81511931,182661737,583534713,847759042,920031027,300910606,980279696,493649584,344263102,656247432,187907941,613845918,294680186,760185876,746539470,269280949,273131460,273268098,58838447,148980077,923723236,769112026,934606914,138972029,998321101,275080101,972211725,472836752,693465030,152879508,496186733,657129511,151385994,718762183,912072704,845324129,107633592,759397384,572479719,975592667,643172909,308550101,889450899,783288023,90914359,77536056,483766031,577620105,392994719,109096164,512378988,816260199,260243647,248086742,387544170,383634333,849216709,269516875,162793954,901554876,28659420,475116448,5023153,74829536,452780543,529408571,27702484,19471758,97013874,95905447,62569372,53748051,74610469,800146634,379618844,448941380,810817838,821033334,668106170,267905205,259750972,945843502,619312426,269973328,958920466,472160712,993278949,427563520,767874623,422991813,516700946,503606884,904893524,964070541,127489673,455722066,179020922,770314060,861958661,212395660,726418380,184240614,546853586,174595399,565192970,148452610,37646449,635445034}
Returns: 377935165

49)

1
3
{1,1,1,1,1,1,1}
{1,1,1,1,1,1,1}
Returns: 571428576

The game consists of just one round in which Teja gains some strawberries. If Teja gains between 0 and 3 strawberries, the game will be competitive, if he gains more, it won't be. The probability that Teja gains between 0 and 3 strawberries is 4/7. Thus, we have X = 4 and Y = 7. We can compute that Z = 142,857,144 and therefore the answer you should return is (X*Z) modulo (10^9 + 7) = 571,428,576.

50)

6
3
{4,7,0,0,0,0,0}
{4,2,0,0,0,0,0}
Returns: 1

This game has six rounds. In each round, the active player gains at most one strawberry. (Note that the probability of gaining more strawberries is zero.) Thus, the difference between the numbers of Teja's and Raja's strawberries never exceeds 3 and the game is guaranteed to be competitive.

51)

7
3
{4,7,0,0,0,0,0}
{4,2,0,0,0,0,0}
Returns: 969874055

If Teja always gains a strawberry and Raja never does, the game will not be competitive. Thus, the probability that this game won't be competitive is (7/11)^4 * (4/6)^3.

Submissions are judged against all 55 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Strawberry with a public method int competitive(int n, int k, vector<int> A, vector<int> B) · 55 test cases · 2 s / 256 MB per case