結果

問題 No.140 みんなで旅行
ユーザー krotonkroton
提出日時 2015-01-29 17:29:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 6,653 bytes
コンパイル時間 1,478 ms
コンパイル使用メモリ 146,444 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-05 07:38:11
合計ジャッジ時間 2,628 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

ll dp[2][600][600];

void add(ll& a, ll b){
	a += b % MOD;
	a %= MOD;
}

void dp_solver(){
	const int n = 555;
	int curr = 0, next = 1;

	memset(dp[curr], 0 ,sizeof(dp[curr]));
	dp[curr][0][0] = 1;

	for(int use=0;use<n;use++){
		memset(dp[next], 0, sizeof(dp[next]));

		int rem = n - use;
		for(int ok=0;ok<=use;ok++){
			for(int ng=0;ng<=rem;ng++){
				ll now = dp[curr][ok][ng];
				if(now == 0)
					continue;

				add(dp[next][ok+1][ng], now);
				add(dp[next][ok][ng+2], now);

				if(ok > 0)
					add(dp[next][ok][ng], now * ok * ok);

				if(ng > 1)
					add(dp[next][ok][ng], now * ng * (ng - 1));

				if(ng > 0)
					add(dp[next][ok+1][ng-1], now * ng);

				if(ok > 0 && ng > 0)
					add(dp[next][ok][ng], now * ok * ng * 2);

				if(ok > 0)
					add(dp[next][ok][ng+1], now * ok * 2);

				if(ng > 0)
					add(dp[next][ok][ng+1], now * ng * 2);
			}
		}

		swap(curr, next);

		ll res = 0;
		for(int ok=0;ok<=use+1;ok++)
			add(res, dp[curr][ok][0]);

		cout << res << ",";
	}
}

int umekomi[] = {-1,1,2,11,87,922,12983,227173,4801548,120540909,523948414,204553930,123189481,77407824,551043005,395334618,981863506,503593909,140719861,26657327,304259086,73882729,910280023,382231666,245250212,222196705,187683297,720954108,221372436,102110221,607730887,491305677,965893625,303648976,925514972,521717794,381165655,328914073,115855325,20568429,862903477,712467022,490875689,598878242,638431266,346674352,700286070,811108428,102646501,588669657,475457136,534657392,205750630,496802474,43012083,735157032,919278154,159550374,247435669,23898598,942315038,427490216,84298681,85237019,470143614,936044526,952272969,393380067,775181642,550745760,219753646,50214977,941851800,565874142,150656718,509391906,599806587,215363270,576957,749154222,549762333,208539583,119462043,657775338,532947722,610424424,264775659,795043453,143289254,154595180,771866270,286772753,334120792,2174219,181638708,216218156,247934282,370502786,373349368,148935939,416998024,989469592,158242445,866659842,976122361,542069790,457275386,339254965,469572756,306910645,147076545,493449877,813490240,928540681,302593417,424540545,114414324,817737652,483600109,280039683,148274535,976389420,584600743,658991534,115068939,614942931,530661135,62672163,638912463,905601675,823242594,363224408,361447527,844774887,500617297,296441919,662835770,597672664,19449882,6997731,463672118,387015384,355192911,692755814,492666004,851323520,573991374,391556593,698552143,916864651,746074609,349854216,732924083,90189290,187590420,272578545,335762799,674058259,383533365,398334208,225491005,555268478,823787598,77388808,419378021,329371541,186417684,261881388,516210714,498752976,211848955,400618028,689639250,149270288,409877494,94786008,427999037,480304186,164321549,319483764,67006474,498472373,990431344,221251494,25490947,643265449,465028389,534240675,899966820,507437193,26541685,141564195,193626725,869042666,320728670,993484553,657871944,591032604,487369552,963137454,966994801,636976043,207078787,670124654,116428676,963048038,85768563,476284321,604759995,916717859,10810762,759975572,367693452,266716686,765674806,873823402,222203545,345850201,126393179,722841690,262667108,958040392,673228148,226264214,2076970,823609800,320120034,115883001,609927990,500471009,557464592,295293279,900185183,576666687,88004332,552703485,124238719,801076574,512929523,290566926,8034439,446181939,583153513,442604887,540281014,345337984,100535908,792264038,270121270,428113821,422016114,456323605,620716328,726185421,788665737,782920197,449448391,295724993,472012884,359861471,727999918,137441508,558087525,127457470,522256627,461867401,592448853,845848162,882176873,85075481,33474756,349499677,293151649,537288332,777643829,193474464,442328289,312992014,949999972,994162079,698619793,554035394,211256162,195659622,380267297,101432535,498167899,11613057,239284399,790186022,571013574,69787021,955819420,786964187,755658617,698084249,226460592,60411005,193502896,190602545,574638828,404024220,383079377,903438555,974204796,642803997,873973203,50408533,482322315,786132451,268392056,532364282,301726827,335736919,216642211,441153964,677678213,844378593,655325118,613987745,327228070,566683523,164821921,214378564,728802668,452510238,878607720,628908890,932040357,88522796,490775763,527276515,94765151,399492901,449291299,224105761,273480417,235835499,979027853,991463729,919611877,955965873,768888638,147835226,714376883,899488922,696399516,607058926,170647329,249660646,450225838,319867813,188211681,50062486,811057485,777160849,372278277,441499697,951112819,846075067,744937190,901708008,600435566,114332157,360522595,99777351,351776020,556174728,852124798,135123628,579592435,645744899,91212234,379006502,776122248,543753901,111011428,146491471,325144497,643435088,324911658,393683202,412832390,578647812,691732189,634063203,430325157,444667109,512103719,486507365,299290764,734899978,793796517,954151793,388325386,730912912,734019541,926943320,700639217,608562500,72659967,721319611,422723347,988310114,950843578,946827911,186384347,927702769,378883774,107131793,554438160,378907330,106980739,647589447,598922514,304862802,849967826,470242155,476873538,749944733,313406618,940807272,747905253,367636781,238219978,683664044,254323072,924976304,108166652,62938594,891189148,369138326,886105608,341455749,162916313,955425745,594117418,477302264,169146305,514346064,750737542,226795888,90858687,137284984,171218407,18266972,959184771,457406302,975501622,972794250,349118334,338268607,394180060,690710745,117063390,112861304,652810836,854411840,631104555,484650549,383799183,368697465,125411564,424762138,214567515,849988263,509862943,724941618,737866580,436731608,485429122,523816840,637858994,288082924,866549443,984238021,924891341,985681280,522508535,946251384,991051683,621738888,818967551,926865122,921988964,426146184,712603730,767006187,701745916,462001464,783285559,94836059,164660782,382258259,974718303,783696448,778323158,115153524,995356112,196020768,932822907,452318534,438765291,523940568,748755899,218274104,430035183,443300682,894145422,983422212,823425582,687312338,856664571,271822797,780061756,138694972,712743532,241009570,1681213,827698624,503515945,479604066,575811306,97458157,395816318,919364681,385095008,809633669,482519144,525341578,325625403,692476604,460102595,471116760,341340274,879431900,900802901,808469391,815175353,947011538,975476212,970057654,432102354,439724372,961329630,430729354,215884455,166041486,815555759,890784148,395672098,389627277,142894633,615047667,119999030,108128895};

int main(){
	//dp_solver();

	int n; cin >> n;
	cout << umekomi[n] << endl;
	return 0;
}
0