题目描述
农夫 John 正在筹划从他的谷仓中售出 N 头奶牛，与此同时也有 N 个农夫想要购买奶牛。每个农夫都有刚好足够购买一头奶牛的钱并且将会把买来的这头奶牛用来挤奶。为了减少买来的牛挤不出奶的风险，农夫们每个人都将会购买两头不同的奶牛各自一半的产权，然后将获得每头牛产奶量的一半。
如果将两种方案中每个农夫都购买了相同的奶牛看作是相同的销售方案。那么农夫 John 一共有多少种不同的销售方案呢？
输入
第一行包含一个整数t ≤ 100，为数据的组数。接下来t行每行包含一个整数N ≤ 2000作为输入数据。
输出
对于每组数据，输出农夫 John 销售奶牛的不同方案数。由于这个数有可能会很大，因此请将答案对10^7 + 7取模后输出。
样例输入
3 1 2 3
样例输出
0 1 6
提示
对于50%的数据，N≤20，
对于100%的数据，N≤2000.
膜拜大佬（不打表会超时，有大佬写的dp,但是看不懂）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e7+7;
map<pair<ll,ll>,ll>mp;
ll f(ll a,ll b){
pair<ll,ll> t=make_pair(a,b);
if(mp[t]) return mp[t];
if(a<0||b<0) return 0;
if(b==0){
if(a==0) return 1;
else if(a==1) return 0;
else if(a==2) return 1;
else if(a==3) return 6;
}
ll ans=0;
if(a>=2) ans=(ans+a*(a-1)/2%mod*f(a-2,b+2)%mod)%mod;
if(b>=2) ans=(ans+b*(b-1)/2%mod*f(a,b-2)%mod)%mod;
if(a>=1&&b>=1) ans=(ans+a*b%mod*f(a-1,b)%mod)%mod;
return mp[t]=ans;
}
ll ans[2005]={0,0,1,6,90,2040,67950,3110940,7530714,8161127,4437954,6791311,8404779,7807258,3766561,7638488,3040893,8460576,8291606,7361971,223729,4222673,6182184,1564381,8014274,2096351,8557871,8907077,5315789,1998105,6981432,6272458,8697276,3693212,6338847,6849115,1357370,2281866,4827709,7397586,9031067,1590465,4251819,8713111,566686,4886978,9419360,4339989,7448532,2462586,1151809,6858506,926090,5064176,1056271,3111849,579285,3497965,5037977,752905,851664,5999194,9161128,1237112,3762644,6822249,3700201,5088066,7694978,3236171,2456444,69532,766630,5962166,6229370,2910370,6002823,4481692,4816800,1604959,8444060,2552096,3805,7578727,9777983,1811616,5645778,5242656,3752078,6188516,8484991,8002908,1718037,9828472,7147825,5128119,4035040,8779827,8551463,5510363,4065217,30047,1272993,3406711,1673424,9197409,9884844,1634545,9774546,5789588,8596909,3285218,8533617,2015755,651964,9426495,7991419,4896656,6214196,8608986,6311424,5165434,7223446,4303865,5661241,543868,6123437,4257853,5769128,9424273,4417520,2007756,2597595,563610,5978378,532438,4223941,6108904,2284400,2430722,2122304,3560098,8468753,8634318,1190641,9788829,3658500,840410,2813038,3488241,8100891,303509,5899731,2475692,8599509,4090018,5176039,8215795,4452281,7668445,8077876,6333920,5841066,2410684,8621039,6348947,202414,8315995,3480334,9014000,771106,3744542,3341785,4267893,2578225,7722854,5247881,3661719,2677831,6202327,7907028,1290798,69006,5528794,1930357,780123,1266941,9095882,5712501,3824299,492223,5548503,4930140,8731422,9335769,9809264,1845218,1078612,2818418,5815469,4813138,7027445,8796304,8992588,7848707,8921922,5623263,5168846,6550209,1752618,7649943,5905060,9591894,3749101,5168406,1933721,7152633,7164016,1556789,3326014,8788330,3928578,2041535,1303190,271556,8175456,601667,2062404,5300749,9011896,358497,2353942,2794396,7327414,3401777,6601598,8760665,9034183,8073360,1027001,7586051,433754,6867682,6329128,1801470,2654180,6126612,5126822,6411646,1712373,8316673,7182204,411078,1659337,1746610,5997201,1183071,5768072,5144010,7817673,3855690,6335522,4339027,2493157,9954336,5553607,67318,5089488,3107121,7426140,585749,7488842,9993813,4529864,9024253,3833300,1712082,12330,7930527,8196493,396591,251475,572282,8677348,6789340,4672974,877093,3519322,4950940,6876671,3084401,2040568,7846938,8343202,1998090,8456024,1257468,4754127,6127769,3278708,3835112,9144141,5725421,281781,6306228,3887621,8119290,9166454,4459776,4514365,4718474,9633247,4438046,356574,2783967,9398572,4490834,4574300,3769991,9868651,6885639,1722979,4109830,1257639,7280854,9017453,3940398,3858836,6763869,6827074,1175397,5741993,7028129,2686676,3009590,1313722,667292,3337908,1307312,4556315,5020869,3668583,2562859,9369996,8831864,4545514,2304405,1013113,7278069,843836,299079,8335452,8915785,7976953,6044325,7567149,9055195,2132637,2020409,760188,3638159,8211036,5729450,7660589,1317970,1232080,204113,2953324,7063694,970457,5014290,847350,6045566,3428057,4597794,1147151,1964912,6939048,3110039,6650613,2478667,5621276,7126823,9910720,3383326,5844455,893396,9962355,5111467,3186128,9653500,3316118,4963654,3477495,1324734,5305777,1635252,4564234,6011893,7043942,3861035,761833,7658640,2314523,2856685,2082573,5351631,5806255,212227,8769579,1259979,7098458,8565358,7070770,3434662,4532449,5213840,2670032,9198065,9567341,4899679,1435209,8846570,8025363,8782216,7075078,9404907,6878190,2455007,8812655,9137438,4892530,653165,1774917,8949792,7102638,4230082,413780,8032667,9663251,9574490,3269309,3864387,890003,1223630,5307876,6345097,2009460,4317956,6631804,3656011,4835083,5317478,7716443,437476,4195695,8643723,6032797,5551747,8308167,7071932,4820338,9477136,7978212,895005,9491715,8997260,1848108,7457375,8108955,6523191,4052747,1250694,5150093,8669464,1116279,4597892,1941214,3867510,1174399,5410195,7263663,8035619,6870895,2236545,4921753,1422365,3291248,2532518,5894197,1684071,6933243,6397609,1294445,2706607,8473265,1720878,6588486,705973,5251858,2634140,8629946,6300924,6445599,5374495,8204855,997909,202462,3336072,9980415,1643702,8654168,6928887,7589480,3388877,9037457,4616047,9344175,4612200,855459,4098353,429869,5276310,870315,1785744,1923253,1801014,5226152,2439600,8720801,78055,3470817,5169090,4282558,4516492,3697603,4661130,845177,5221737,7952076,1746797,161889,5735409,4054564,6390933,4254201,5637608,8180402,5600723,8385817,6772514,6235656,6994010,2862006,8082261,3217083,9891346,8125566,803977,3543098,1723327,8814364,3973319,3787075,1979315,7955351,7884323,9651376,2683606,2739787,5378160,5955843,7445820,7264931,5709418,7145911,5471216,9565557,236073,5215093,6331620,2416358,8022181,2587065,442,7234211,8296771,9389206,5664425,3812743,5298318,4893441,8916646,3758234,886244,3708116,292508,9275850,2614828,9026359,4499682,7283813,4880717,5595674,8577962,4725686,9043333,926862,2849404,8873409,5279302,3041548,5563880,1425678,2345077,975772,8459926,2385641,9600259,7052085,9061512,9388409,3147344,207872,3372593,7603595,6830615,8872654,1192704,9487378,6626491,9051378,436816,2146974,3550954,9034193,7579805,440570,9893306,4183997,3087925,2351902,1172914,8942196,8692881,7737466,9243436,5959997,7346862,2177237,9696144,7745200,6212434,7705933,3119353,494714,9324359,2988722,2925183,398592,1511749,1142177,9583371,9932557,9332673,9422850,9781766,8705482,960015,635078,6650271,8802223,8502412,1322171,1662541,2303272,5230917,7174220,3456311,2121494,3386356,8939440,734040,8966347,3614360,5704160,1105446,2044571,91968,7976743,3811563,2135587,230660,7807273,5271717,9970439,1247386,5505428,3336719,1405439,5433818,4717276,6520858,5694567,5891115,7434365,6190056,4465164,5097436,8343707,9174787,3693288,3115041,4319619,2293552,3691969,2842829,9202082,1726944,3088262,6363251,9544508,2271017,4586681,8076819,5450787,214970,190682,8575459,138582,9572018,5616107,9825705,7402388,8016473,6936346,6042652,6614657,430368,7782250,8317802,2171157,4787079,540976,7888512,3237361,5739005,9188430,7358017,3502692,7923884,2530219,4936176,5684547,2926118,6687065,5041999,8587041,7461310,7357245,8804807,5662441,5198672,1503546,4771274,5020205,9868907,2974278,5652663,3389130,4339808,505066,9711560,6239883,388211,1620878,3985627,7811186,6879761,415984,7818896,4467260,676933,897991,6270328,2081013,582538,6280610,1276141,9491116,9441689,6525342,8060824,6572014,5752516,6975100,8887658,2309380,1573684,9501374,8423708,7214534,819284,5718855,2267297,5282112,6635801,1322409,3224740,7594037,3962891,9134101,5181896,5016760,8549989,7938581,7216295,3288013,9330933,3030775,9673262,4951908,150272,5632579,9082886,5420352,3247259,6684712,4484249,5237709,5967048,6531614,6298632,759680,9033068,1914761,3884268,2096428,4639866,3140298,2762926,7888971,6150706,2547077,7227752,4153079,9417386,478790,6833833,2849303,8235154,4462367,8009930,1893324,7802213,5093984,4162109,7857989,8613261,9012753,8642488,581189,6670088,7775348,2496162,6199057,4051740,8968446,8621412,875827,5250390,3374917,821920,2649500,3341662,4034915,2071792,1963787,7764371,763564,8375994,8839062,7366479,2272865,5583554,630580,786756,5173563,5427875,2536381,3400196,5300943,1685574,1609718,1425355,3000998,5596595,1878796,2230674,9612980,9644823,2920607,6917900,4349151,7217953,3870273,8114605,212320,2468934,6174980,9157125,9702684,2619726,439978,3509048,8708209,3308451,1590151,8145851,6192714,7465150,3050471,3657764,5296780,3251783,6994768,4592061,848338,6454177,1613724,3142705,4251472,983940,6083395,8624497,165533,4176313,1429101,1147551,7262326,468932,205138,9041128,6491018,5413573,6910704,8440770,1488662,3051663,9853211,8334437,3988899,6453378,322763,9118290,6886238,3605912,8608268,9668775,6018636,2567048,6005462,5432393,4943073,324645,1454786,5678935,9558678,3203164,3811991,6310346,4624074,4835799,9693241,7513885,3571095,2539759,9721471,6990689,1849065,8912211,9431643,112920,7768896,2841820,1832127,8390897,6827896,1830245,5704342,3556039,4609959,1140492,6304700,3165524,4845209,6422325,2488004,3909855,1112262,3174934,8028612,1089678,1501836,9903084,5799383,62106,9552091,5981937,4828271,9864503,2193471,6961518,8456767,7487537,9772285,6445850,2008094,5987583,64929,8738126,1850947,4870616,7702085,8682607,9577498,4373768,4056651,4548794,2859699,8421950,2258400,1594995,2308273,6803430,6184252,7085730,8648731,6650047,8881158,5758920,9394003,6694274,6190839,1768139,4815097,9050538,7154423,3216338,8735303,6634050,1578998,9805220,1113203,8552749,2138893,2491768,2053262,9716766,4754873,7290868,6036515,8568746,8369254,1335279,6888120,290769,1500895,1457609,9698887,717983,5408868,5842669,4464104,6224715,5981937,6906940,75280,1624166,2072082,2061731,2012799,5762684,9997184,2870050,7678560,7368030,8519814,3366898,5816321,1543240,5212199,2281925,4430228,4529033,4953424,4408585,8112361,7400965,2666794,3919265,2434367,8545221,8626147,401807,915593,7845117,3113769,4673947,4981654,7433900,5466269,6026164,7492242,8610150,9265086,1357863,7678560,9441994,6156963,2073964,5251721,4371886,3515576,7959919,516609,2427780,9080650,9275437,9406236,4977890,8042727,5681758,8754123,6179547,1138610,565541,8948910,2788183,9105116,1309872,132681,9465519,4246733,8701427,5719398,6182370,3617204,9716766,1483957,1139551,2773127,5322296,5563192,2064554,8282682,2889811,2252754,1825540,7878052,9328133,692576,3514635,6089211,1461373,6807194,6821309,2284748,4132872,9603846,6830719,2649856,3501461,1819894,5137860,5333588,9024190,3716950,7428254,3877861,4407644,2434367,1768139,8952674,5525552,9337543,2833351,2224524,6475021,4282491,4582670,3146704,5721280,2816413,6397859,210784,5932064,2222642,3866569,5933946,7506357,7416962,1429379,988050,2996144,4528092,1131082,6858008,7110196,676579,279477,4865911,1469842,1729558,7168538,8632734,9239679,4157338,9559619,7639979,5794678,8627088,1796369,7617395,4935545,572128,9928491,8731539,6898471,4619369,3918324,4851796,502494,9923786,2381671,4631602,4087704,265362,2520939,6961518,7895931,9316841,1606287,9196393,8944205,5078577,6897530,4294724,6451496,6793079,6204013,5025881,5733513,1436907,1241179,4524328,8789881,4956247,897714,1582762,4438697,9889910,8277977,1818953,203256,3468526,7230644,2030678,1394562,4104642,4441520,3731065,1585585,7070674,3708481,7306865,1525361,6224715,9691359,6220010,7938276,2161477,9078768,3358429,812083,85631,8758828,2720431,2520939,5005179,6619935,2675263,7574109,3340550,8361726,3953141,7467776,1084032,4194978,7079143,6566298,5677994,1232710,7521413,7256051,9444817,9242502,1764375,6332930,5875604,9798633,9876736,4954365,3910796,3407361,1499013,3242686,4363417,2694083,5540608,2151126,3261506,6006403,3277503,6921996,202315,4984477,5873722,724570,4795336,5901011,3275621,6030869,1206362,7186417,6920114,2224524,2264987,8911270,8916916,1378565,6815663,6665103,937236,1874472,9317782,9403413,3511812,7487537,2246167,7062205,3888212,9583144,3804463,9379888,6788374,1077445,2298863,4630661,6229420,750918,5114335,5075754,2249931,5301594,3633201,7096081,1015339,9741232,7580696,6616171,4409526,8121771,2301686,1203539,2559520,6848598,9741232,6120264,8088836,2220760,3063896,3361252,4501744,2716667,6903176,7824415,7158187,6544655,5517083,5789973,178790,6531481,9931314,651172,2287571,9173809,3815755,4792513,9470224,6868359,5739159,5869017,5838905,663405,3475113,5978173,9054302,2317683,8248806,5070108,2310155,3531573,383928,6481608,2906749,7859232,6925760,5746687,3684956,417804,7500711,4567614,3688720,3349019,8289269,104451,6174842,8891509,1437848,9567147,4545971,5399458,6470316,6087329,3101536,9620784,2793829,6689569,9043010,5624357,8912211,4824507,6650988,4277786,9250030,9555855,7454602,4545971,5817262,7563758,5152916,5783386,5541549,7226880,6351750,9404354,1756847,610709,2023150,6147553,2473889,8380546,4551617,1568647,5180205,5004238,427214,1265645,845018,4870616,2337444,8884922,6388449,4652304,5999816,2239580,2742074,4897905,4658891,8981845,6724386,7384968,9573734,9763816,7854527,8644026,7734079,909006,1674039,3383836,6482549,1593113,1751201,1597818,3929616,4001132,5126568,4099937,8853869,8121771,9133346,9732763,6009226,1666511,1359745,6604879,8426655,6424207,3969138,4023716,7026447,9076886,2282866,3995486,2755248,8574392,941000,4630661,9732763,4570437,7161951,7908164,6751675,3412066,2198176,4841445,8277036,2292276,4223208,3781879,6469375,5665761,6761085,2551992,4299429,6953990,9732763,6996335,1706033,1308931,402748,7547761,8346670,9747819,629529,4840504,587184,3731065,7033034,881717,3281267,5141624,1518774,8585684,1786959,6215305,2334621,6598292,1569588,5911362,8275154,719865,5837023,8381487,9438230,2641387,5173618,1815189,9047715,4662655,6638755,1206362,4098055,1691918,5615888,4299429,4445284,2301686,2341208,9395885,2553874,8921621,9395885,3021551,8769179,7825356,2662089,5020235,9538917,5565074,5432393,6866477,9706415,6727209,6920114,3518399,3141058,8134004,9069358,1899879,8931031,3553216,550485,8517932,7692675,3743298,6322579,2398609,1202598,6297172,8049314,7817828,6697097,7366148,9317782,1307990,7427313,8899978,7508239,8087895,562718,1337161,3595561,7443310,6922937,2930274,8775766,9390239,5214081,3584269,2006212,6642519,8253511,8816229,1046392,7907223,3475113,1924345,441329,2121014,3496756,2294158,6949285,2121955,1611933,84690,876071,2312037,5659174,3131648,2922746,8726834,4193096,6476903,1261881,7638097,8967730,1688154,5988524,3554157,2571753,3734829,2025032,9713002,9836273,4859324,6653811,5001415,6605820,8650613,2583045,1671216,9486221,4750168,5120922,6153199,2004330,1589349,7796185,282300,4441520,1570529,202315,3404538,1727676,1310813,1560178,2535995,8609209,8437947,3781879,226781,7774542,4388824,9422233,7437664,8402189,7258874,997460,9576557,4002073,5207494,7003863,5784327,3329258,2695024,7237231,4258025,6507956,428155,9675362,6300936,1617579,7416962,3121297,3460998,5533080,9993420,8222458,9647132,8505699,6096739,281359,5566956,6921055,6858008,4713469,6890002,9652778,3713186,1085914,3375367,6884356,3139176,3358429,7894049,9923786,4649481,5731631,2087138,8687312,2189707,9186983,2186884,6124028,5028704,7338859,2508706,8957379,546721,2634800,7701144,6569121,285123,5263013,7086671,6622758,7869583,8579097,3649198,9715825,7853586,9832509,5920772,4903551,8289269,7343564,4058533,7884639,9765698,8435124,4728525,9260381,2492709,7498829,8498171,9873913,7312511,6370570,9132405,1722971,8618619,7955214,9024190,3417712,4851796,9056184,1524420,8736244,4711587,5485089,5578248,4256143,7567522,5953707,3983253,4773693,2153949,1595936,2377907,6404446,5053170,596594,9619843,2504942,6333871,5048465,6761085,6319756,5585776,2787242,3748944,645526,7787716,2409901,4561027,8379605,5089869,2955681,2245226,4075471,2470125,3482641,0,8073780,9327192,9863562,2255577,8590389,3364075,5530257,3038489,4973185,9578439,7553407,274772,4142282,9850388,6992571,4296606,2058908,3894799,8102951,5235724,3021551,1707915,1203539,5791855,401807,9800515,4551617,9042069,5112453,3113769,4274963,5292184,5251721,6348927,2996144,2441895,1935637,1527243,2539759,3018728,6440204,5972527,9358245,5751392,6617112,4671124,4609959,7931689,5912303,3457234,3850572,4808510,6940816,701045,7378381,8219635,4892259,7405670,6078860,6331048,2484240,3025315,5102102,9820276,6972810,5748569,3917383,7512003,1906466,838431,5729749,1706033,1491485,5551900,6827896,5484148,4571378,5508614,7120547,1268468,1055802,5377815,9375183,1177191,8169762,4692767,2750543,281359,3696248,5559428,9384593,6205895,425332,7072556,2918041,3949377,5346762,9227446,7946745,5044701,3430886,8852928,5279951,5981937,2316742,6102385,5521788,7782070,6587941,509081,5099279,5458741,6997276,9389298,4925194,2717608,6046866,1437848,189141,3879743,1017221,5648823,3499579,2214173,5270541,7910046,3057309,6711212,6652870,6924819,5463446,3459116,4479160,3835516,8697663,4651363,5575425,6694274,244660,9789223,4933663,9513510,3273739,6481608,9779813,8881158,707632,9154048,3470408,7317216,5644118,2131365,8871748,3349019,1135787,6001698,7347328,2627272,11292,5116217,6684864,2642328,2706316,6520189,7607985,8197992,6645342,7193945,371695,5411691,1422792,6663221,1862239,8778589,427214,7507298,};
void init(){
freopen("打表.txt","w",stdout);
for(int i=1;i<=2000;i++){
printf("%lld,",f(i,0));
}
freopen("CON","w",stdout);
printf("OK\n");
}
int main(){
//init();
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
printf("%lld\n",ans[n]);
}
return 0;
} 简单的文件读写
freopen()
freopen这个函数，在ACM中应用很广，因为ACM试题中可能有大量输入数据，程序运行往往不是一次成功的，每次运行都重新输入很浪费时间，因此freopen就可以解决测试数据的重复输入问题。
函数声明：
FILE * freopen(const char *filename, const char *mode,FILE *stream);
参数说明：
filename：要打开的文件名；
mode：文件打开的模式，和fopen中的模式（r/w）相同。
stream：文件指针，通常使用标准流文件（stdin/stdout/stderr）
使用方法：
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);fclose(stdin);
fclose(stdout);
freopen()函数重定向了标准流，使其指向指定文件，因此不需要修改scanf和printf。
确实很方便吧，不过还有个问题要解决。通过freopen我们把标准流重定向到了指定文件，那么如果我们想让一些信息输出到屏幕，该怎么做呢？
fopen函数由fprintf和printf两个函数，分别输出到文件和控制台。而freopen函数，需要修改函数的filename参数，让标准流输出到控制台。而这个控制台设备文件的名字与操作系统相关。
DOS、Win系统：
freopen("CON","r",stdin);
freopen("CON","w",stdout);
Linux:
freopen("/dev/console","r",stdin);
这样就能实现一部分需要的数据输出到文件，同时另一部分数据输出到控制台。这样让程序拥有一些简单的交互能力。
京公网安备 11010502036488号