BZOJ 4321

发表于 | 更新于

Link

状态状态。。

Solution

心路历程

一开始，觉得必须需要知道最后一个数字的位置，就可以推合法状态了。写完之后忽然发现自己zz了：不合法状态也可以转化成合法状态。 然后发现，并不需要知道最后一个数字的位置，因为仅仅从合法状态来说，最后一个数字不管在哪，都是少了两个可以放的位置。 然后发现必须要知道有了多少对不合法的，然后想转移。 然后发现，最后一个数字和其它的数字不能一起算，然而又已经删掉了最后一个数字的位置那个状态，所以就无力了。。。 其实就按照这个思路接着想，只差一步了

最后

f[i][j][0/1]f[i][j][0/1]表示前ii个数字，在1∼i−11\sim i-1中有jj对不合法的，i−1i-1与ii相邻/不相邻的方案数目。 转移需要花点脑筋，而且还有一个我觉得很容易漏掉的好吧就是我漏掉的部分 ↓\downarrow

f[i][j][1]+=f[i-1][j][1] ↑\uparrow

Why Can't

没有继续大力分析，没有继续把问题抽象下去

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "lucida"
using std::max;
const int P=7777777,MAXN=1000+11;
int64 f[MAXN][MAXN][2];
int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	//f[i][j] 前i个人的排列 最后一个人为j
	//只要知道最后一个数字的位置??
	//并不需要知道 只需要知道少了两个可以待的位置就行了!
	//f[i][j]表示前i个数字，j对不合法
	f[1][0][0]=1;
	for(int i=2;i<=n;++i)
		for(int j=0;j<=i;++j) {
			(f[i][j][0]+=(f[i-1][j][0]*max(i-j-2,0)+f[i-1][j-1][1]*max(i-j-1,0)))%=P;
			(f[i][j][1]+=(f[i-1][j][0]*2+f[i-1][j-1][1]+f[i-1][j][1]))%=P;//f[i-1][j][1]....
			(f[i][j][0]+=(f[i-1][j+1][0]*(j+1)+f[i-1][j][1]*j))%=P;
		}
	os<<f[n][0][0]<<'\n';
	return 0;
}

打表(2333)

1
2
3
4
5
6
7
#include<cstdio>
const int Ans[]={0,1,0,0,2,14,90,646,5242,47622,479306,5296790,1556818,6839196,2618495,979672,2780742,6351756,1622080,2317213,2571415,7589087,5658722,7608399,6636261,4668421,7151323,3463698,4156794,4264499,5635853,6694840,2815244,6087105,2410849,138105,6232687,4045091,5426290,443641,2132596,7300720,3837755,683117,6707322,4505086,6965880,4427426,4624186,1633284,5054300,3707705,280807,7350611,6884553,3601801,2427241,4950492,1686306,6296813,4597759,5133390,5889499,3818810,666987,1669662,5049011,2299852,4731598,3071649,7354002,6093291,4043220,1517871,2203318,2339158,2233651,6915925,5535396,569059,6518458,1643343,621793,649215,5700623,268360,2406235,1576587,6770258,5337622,4162333,1050359,1253251,4101392,7401333,1827870,2681459,3743523,767947,2646862,3207770,517802,2948811,2480880,6880517,6183333,6979293,2934653,87516,6316788,2579861,1413692,2938668,3198980,7690710,162125,5876967,7050837,4544169,2517853,2984897,3852570,4068038,3755810,336753,5648517,5964467,7579328,1314739,4905010,4341055,5881025,5615323,1813051,5787382,1140427,6724244,4113573,6909270,9863,4911548,5192356,2816477,370921,5745668,1055932,4968796,6466084,2348198,7041350,2985873,3279516,6465764,2591925,3393346,3641471,1461389,950381,846340,2553519,1746115,3881145,1358265,2790180,5474331,2029449,6639168,1269072,3724565,3750419,4938996,5057232,7292220,1879531,5663210,6177075,5875876,2328453,5066616,4617531,6466296,5290250,2692625,3618119,6072464,4404510,3069673,7253998,5204843,3508227,4711097,7126610,6893147,5853766,890320,5559204,6971508,1003094,2774848,1158190,5604562,4161951,1328313,3024947,4528131,7115669,837972,4659265,4950229,1073009,1734654,7312166,6810327,4622343,5561337,2255844,232841,5930773,3738510,4039897,4343355,4877777,4282219,2043160,7373280,5959493,2364466,2345138,6021713,5408420,2138843,2578676,3491914,5491991,2938693,2343511,3835038,918729,3506445,7255536,4830895,584295,6602573,677442,4971995,4163084,4054588,5432974,1891297,5678780,4514570,6885081,446143,7468721,5312285,4974429,2888443,3987105,432075,776113,3374867,6819492,4062998,484283,6198973,4110260,6414532,4706486,4842032,2831757,5202818,4559439,5282403,1989577,1572353,289031,7713127,4452303,3527710,7513065,4843165,386289,5234326,4148807,2818226,1888967,2812397,1802929,873242,6212207,6248566,3194263,4409318,3206462,1353966,1969724,1347366,2232725,5499730,7045825,5609856,1573336,2239754,3766001,2586180,5716216,425471,3659229,2834648,6287737,3636051,3399590,2466721,2128276,4461870,5344761,6785267,6957056,2179774,2733593,3772234,7289702,4035666,3851765,4477899,3768252,4038221,7054071,5834549,5453121,287174,4048255,5253243,4392271,7179323,76811,146102,1578424,3268670,4207173,5855407,3773962,5003425,2235067,2802967,2729084,3455188,1119785,4035420,1732297,778944,824139,1100826,95541,5544432,1566498,1567440,551322,5215629,3604182,7771269,7685155,2216764,1285347,918300,2396983,7217825,3369371,3315093,5588110,1245062,6643695,7636138,1633962,5819872,3776537,3646486,2724022,7351566,2831116,6313418,890839,3227467,1511926,1427979,3772960,756685,3873451,531407,6240922,1128705,4731741,4193026,1297066,4906586,3934726,7375604,47022,1998717,760307,46192,207187,665821,4981461,5687210,1772596,128959,2076733,5990543,7355955,565388,2833764,5905004,5258304,4921608,6612810,2044310,1662838,5450645,452424,3389090,2672699,5626837,2839961,2737467,5020305,5290691,829642,4138448,6228139,4044098,619733,2027519,4508749,3669755,282920,1162580,3158377,4593034,2850970,5237736,976495,2895815,2072645,6870551,4647442,2358136,6248207,6739395,5526095,2209892,6636481,1031973,6618286,1749713,642721,7545831,2940204,288010,3862217,2559113,2611315,1232348,3650431,4818813,4964874,4839700,7154843,110432,6379298,3883053,6804568,6186042,6011504,4339115,738101,7690765,4756501,2851057,5569429,3025083,2393387,7449036,2562002,6323519,4969574,6272051,1479081,6100574,7398146,5877758,2186920,5000148,6374576,7473408,6703105,1402345,2454328,6075061,822690,3304548,1830264,927490,3950401,518453,5888471,5975619,3786585,6959356,2883030,4177684,6996222,170505,6207097,3076089,351689,4133294,5417104,5800191,6859231,1820398,3467903,4516377,2527248,64141,1494383,2632433,6170088,3650845,3295182,91270,644098,7445051,4119851,4422809,1527804,5888734,4496684,2567950,6292344,2458833,2797649,934173,4120160,5905876,345065,6425137,1074914,4446231,5024353,1717161,6469011,28938,663007,2219111,4383681,7453210,4971584,1450341,6822158,149651,3827195,7260301,6879381,6668639,917444,5072550,6159666,3935994,2674036,1598837,2814919,1680480,4448983,5955549,1166964,1842861,200415,5878388,7083814,1635564,4702126,4493978,6915490,20372,7003691,2470234,5461484,244711,4479056,3846877,472750,5611779,4681183,3740975,375391,2063816,5658871,1791960,211570,631089,2515436,787022,4246012,3143993,5882721,6783110,325594,3667643,6446197,5730052,6427100,1900131,5808434,5153698,635677,335417,3106118,369333,7031386,488430,113753,6070827,5165792,4356386,94872,7490282,1718061,4268625,7463106,4475973,2415085,4483149,4799443,2880120,102945,1186696,1019853,3992925,5600183,7216631,5725995,7333253,1047571,6906450,1896805,6601118,2557770,685200,3607313,6624422,3884197,4602597,3614038,6845519,7057766,3851131,3731735,2409601,5397267,6871766,427033,4123782,3163443,2346631,5381854,6787766,1240247,2524041,3323077,7512481,4944828,6597820,1519652,4814711,6626191,2574038,166890,2660609,7300204,6408366,7135493,1279091,2671524,2306980,5673220,4950377,6999042,2964380,6184505,564828,402027,353822,4236759,5224729,3291863,7175471,7654677,3083840,6959540,4086899,3118886,4329779,3070338,4342742,3918694,5865160,4989350,6770721,2822331,4405249,4502038,1724209,2852395,5346122,3106538,7120126,1247076,3930582,1932255,24815,7506389,5470310,7359948,4973782,4046296,3594889,5490926,4626900,645030,5696256,5475461,5986265,5353722,5391729,987177,5492661,5339818,625172,4352056,1266220,6247290,2603935,6359011,5753936,5157479,6626884,5160095,5931051,774874,4848857,4480435,7318152,1734742,4347529,1144304,7089766,5413689,3183788,925951,6510586,4902852,2825396,6230163,4192383,7534388,6073643,7110847,932250,3779335,1030097,7064639,4830699,6653407,810094,4256577,1367898,3055481,1775101,2598646,4483964,689593,7225887,1610196,1476354,6033455,3397015,692508,4410411,1590599,5925290,3627045,3280493,2052058,2846069,1441414,7281229,3077753,7294138,633074,2695832,1699570,4879180,6690505,3048283,4151177,2511732,4447409,1748420,1354964,7400180,3727612,1862768,4707914,5846252,3208882,230263,2645786,4878853,66355,6495502,6956034,73348,2846433,2719546,334670,5976339,6744844,2100853,3210793,3265449,88371,4015788,1342077,7605058,4743621,5455585,7184641,276707,4597992,1069325,947640,2042795,4484170,3322842,2933913,3656863,6447793,538817,189022,5140739,6875710,3817769,466865,387721,3321522,241555,2383708,188326,1613097,2901710,5193960,4042639,2881012,7414269,3856960,7412934,5139610,3728786,1131684,2583839,5060599,3552890,5903369,5746580,4413313,4469499,1098014,6419366,2470995,5287125,1931104,6943872,1682493,5027742,453206,7743608,4758981,3712779,4903026,2975342,1667807,1862408,2788571,3963719,4772467,1407243,1913192,1451995,3162171,6325912,5795674,159852,5665844,4960871,5456921,7553758,849683,645040,585795,2481141,4085719,3004140,2779992,6984381,6413557,3270169,1433700,559789,1742490,1190072,3712424,3839553,1431458,2813431,23213,5220550,5215873,2315052,5590378,6596849,3616685,2144302,7264216,7541529,1240675,4149772,7416864,6251663,123803,2673040,7214877,4169450,5824318,252812,3959174,1791558,4762941,7289998,4696827,1390029,7170415,3191676,32334,2929646,7404143,6245335,3897624,3388602,5565156,833755,3952026,3655801,108075,7545682,2888942,1801203,6528425,1170175,6440642,2967214,4498665,5912977,6195947,5592971,3864428,1720959,7098352,1578490,5075406,138073,569507,5628034,2607001,2401852,5992794,799848,1795341,5182918,3154775,5586723,3174187,6588194,3257212,4831174,585719,5954346,1458070,371341,6845212,496636};
int main() {
	int n;scanf("%d",&n);
	printf("%d\n",Ans[n]);
	return 0;
}