結果

問題 No.140 みんなで旅行
ユーザー antaanta
提出日時 2015-01-30 00:15:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 9,754 bytes
コンパイル時間 988 ms
コンパイル使用メモリ 100,436 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-23 04:19:24
合計ジャッジ時間 1,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt(): x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }
	
	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	
	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;

void precomp(int N) {
	vector<vector<mint> > dp, ndp(N+3, vector<mint>(N+3));
	vector<mint> ans(N+1);
	ans[0] = 1;
	ndp[0][0] = 1;
	rep(i, N) {
		dp.swap(ndp);
		ndp.assign(N+3, vector<mint>(N+3));
		int g = min(N, 2*i);
		rer(j, 0, g) rer(k, 0, g) {
			mint x = dp[j][k];
			if(x.get() == 0) continue;
			//夫婦が同じグループに入る
			if(k > 0) ndp[j+1][k-1] += x * k;	//夫婦なしグループを解消する場合
			if(j > 0) ndp[j][k] += x * j;		//夫婦ありグループに入る場合
			ndp[j+1][k] += x;					//新たなグループを作る場合
			//新たなグループ, 新たなグループ
			ndp[j][k+2] += x;
			//新たなグループ, 既存のグループ
			if(j + k > 0) ndp[j][k+1] += x * (j + k) * 2;
			//既存のグループ, 既存のグループ
			if(j + k > 1) ndp[j][k] += x * ((j + k) * (j + k - 1));
		}
		rer(j, 0, N) ans[i+1] += ndp[j][0];
	}
	rer(i, 0, N) {
		if(i % 8 == 0) cout << endl << '\t';
		else cout << " ";
		cout<<ans[i].get() << ",";
	}
}

const mint precomputed[556] = {
        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() {
//	precomp(555);
	int N;
	while(~scanf("%d", &N)) {
		mint ans = precomputed[N];
		printf("%d\n", ans.get());
	}
	return 0;
}
0