首页 > 代码库 > Poj1737
Poj1737
题目连接:
http://poj.org/problem?id=1737
题目大意:
给1<=n<=50个不同颜色的点,求使它们联通的不同方案数目.
分析:
感觉组合数学题目最重要的是不重不漏,找到划分的标准，首先想到从反面做,然后:
想法1:
c(n,k)取出k个,这k个是联通的,剩下的随意,联通不联通都无所谓,稍微想一下发现不对,因为肯定有很多重复情况,因为n-k个中如果有k个是联通的,那么前面c(n,k)包含了取前面k个联通和从后面n-k个里面取联通,而这种重复似乎不容易去掉.
想法2：
想法1失败的原因是因为前一次有可能取到了后一次的,究其原因是因为第一次取的没有固定。所以需要固定一个一定要联通的,假设就是编号为1的点,这个点是一定要取的,然后从后面的n-1个点中再分别取k=0-(n-2)个与第一个点构成联通,剩下的(n-k-1)个点随意.这样看来肯定是没有重复的了,那么看看有没有漏掉的,因为是一定取第一个点作为联通的那部分,所以想象一下任意一种不联通的情况，对于1这个点,它一定是与0-n-2个点联通,然后整体是不连通的,那么我们把联通的那部分拿出来不就是第一步的取法么,然后图已经不连通了,剩下的就随意.所以看到是没有漏掉的情况.
最后确定公式:为了方便记x(n)为n个点的最大边数,不难发现x(n)=n*(n-1)/2
f[n]=2^x(n-1)+f[2]*c(n-1,1)*2^(n-2)+...f[1+k]*c(n-1,k)*2^(n-1-k) (0<=k<=n-2)
x(n-1)最大为49*48/2=1176.
所以必须使用高精度,然后打表.
打表AC代码:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 char listt[55][550]={{"1"},{"1"},{"4"},{"38"},{"728"},{"26704"},{"1866256"},{"251548592"},{"66296291072"},{"34496488594816"},{"35641657548953344"},{"73354596206766622208"},{"301272202649664088951808"},{"2471648811030443735290891264"},{"40527680937730480234609755344896"},{"1328578958335783201008338986845427712"},{"87089689052447182841791388989051400978432"},{"11416413520434522308788674285713247919244640256"},{"2992938411601818037370034280152893935458466172698624"},{"1569215570739406346256547210377768575765884983264804405248"},{"1645471602537064877722485517800176164374001516327306287561310208"},{"3450836972295011606260171491426093685143754611532806996347023345844224"},{"14473931784581530777452916362195345689326195578125463551466449404195748970496"},{"121416458387840348322477378286414146687038407628418077332783529218671227143860518912"},{"2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472"},{"68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896"},{"4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344"},{"615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208"},{"165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128"},{"88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584"},{"95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256"},{"204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592"},{"878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592"},{"7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336"},{"129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304"},{"4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888"},{"306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568"},{"42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144"},{"11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376"},{"6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752"},{"6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392"},{"15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376"},{"67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304"},{"594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488"},{"10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328"},{"368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504"},{"25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056"},{"3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992"},{"1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672"},{"577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016"}}; 5 int main() 6 { 7 int n; 8 while(scanf("%d",&n),n) 9 {10 cout<<listt[n-1]<<endl;11 }12 return 0;13 }
再附一个打表的程序:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 150; 9 const int MAXN = 1000; 10 11 struct bign 12 { 13 int len, s[MAXN]; 14 bign () 15 { 16 memset(s, 0, sizeof(s)); 17 len = 1; 18 } 19 bign (int num) { *this = num; } 20 bign (const char *num) { *this = num; } 21 bign operator = (const int num) 22 { 23 char s[MAXN]; 24 sprintf(s, "%d", num); 25 *this = s; 26 return *this; 27 } 28 bign operator = (const char *num) 29 { 30 for(int i = 0; num[i] == ‘0‘; num++) ; //去前导0 31 len = strlen(num); 32 for(int i = 0; i < len; i++) s[i] = num[len-i-1] - ‘0‘; 33 return *this; 34 } 35 bign operator + (const bign &b) const //+ 36 { 37 bign c; 38 c.len = 0; 39 for(int i = 0, g = 0; g || i < max(len, b.len); i++) 40 { 41 int x = g; 42 if(i < len) x += s[i]; 43 if(i < b.len) x += b.s[i]; 44 c.s[c.len++] = x % 10; 45 g = x / 10; 46 } 47 return c; 48 } 49 bign operator += (const bign &b) 50 { 51 *this = *this + b; 52 return *this; 53 } 54 void clean() 55 { 56 while(len > 1 && !s[len-1]) len--; 57 } 58 bign operator * (const bign &b) //* 59 { 60 bign c; 61 c.len = len + b.len; 62 for(int i = 0; i < len; i++) 63 { 64 for(int j = 0; j < b.len; j++) 65 { 66 c.s[i+j] += s[i] * b.s[j]; 67 } 68 } 69 for(int i = 0; i < c.len; i++) 70 { 71 c.s[i+1] += c.s[i]/10; 72 c.s[i] %= 10; 73 } 74 c.clean(); 75 return c; 76 } 77 bign operator *= (const bign &b) 78 { 79 *this = *this * b; 80 return *this; 81 } 82 bign operator - (const bign &b) 83 { 84 bign c; 85 c.len = 0; 86 for(int i = 0, g = 0; i < len; i++) 87 { 88 int x = s[i] - g; 89 if(i < b.len) x -= b.s[i]; 90 if(x >= 0) g = 0; 91 else 92 { 93 g = 1; 94 x += 10; 95 } 96 c.s[c.len++] = x; 97 } 98 c.clean(); 99 return c;100 }101 bign operator -= (const bign &b)102 {103 *this = *this - b;104 return *this;105 }106 bign operator / (const bign &b)107 {108 bign c, f = 0;109 for(int i = len-1; i >= 0; i--)110 {111 f = f*10;112 f.s[0] = s[i];113 while(f >= b)114 {115 f -= b;116 c.s[i]++;117 }118 }119 c.len = len;120 c.clean();121 return c;122 }123 bign operator /= (const bign &b)124 {125 *this = *this / b;126 return *this;127 }128 bign operator % (const bign &b)129 {130 bign r = *this / b;131 r = *this - r*b;132 return r;133 }134 bign operator %= (const bign &b)135 {136 *this = *this % b;137 return *this;138 }139 bool operator < (const bign &b)140 {141 if(len != b.len) return len < b.len;142 for(int i = len-1; i >= 0; i--)143 {144 if(s[i] != b.s[i]) return s[i] < b.s[i];145 }146 return false;147 }148 bool operator > (const bign &b)149 {150 if(len != b.len) return len > b.len;151 for(int i = len-1; i >= 0; i--)152 {153 if(s[i] != b.s[i]) return s[i] > b.s[i];154 }155 return false;156 }157 bool operator == (const bign &b)158 {159 return !(*this > b) && !(*this < b);160 }161 bool operator != (const bign &b)162 {163 return !(*this == b);164 }165 bool operator <= (const bign &b)166 {167 return *this < b || *this == b;168 }169 bool operator >= (const bign &b)170 {171 return *this > b || *this == b;172 }173 string str() const174 {175 string res = "";176 for(int i = 0; i < len; i++) res = char(s[i]+‘0‘) + res;177 return res;178 }179 };180 181 istream& operator >> (istream &in, bign &x)182 {183 string s;184 in >> s;185 x = s.c_str();186 return in;187 }188 189 ostream& operator << (ostream &out, const bign &x)190 {191 out << x.str();192 return out;193 }194 195 bign times2(int n)196 {197 bign a="1";198 for(int i=1;i<=n;i++)199 a*=2;200 return a;201 }202 bign c(int a,int b)203 {204 int cc=a-b;205 char ini1[5]="1";206 bign res1,res2,res3;207 if(b==0) res2=ini1;208 else res2=b;209 res1=a,res3=cc;210 for(int i=a-1;i>=1;i--)211 {212 bign tp=i;213 res1*=tp;214 }215 //cout<<"res1="<<res1<<endl;216 for(int i=b-1;i>=1;i--)217 {218 bign tp=i;219 res2*=tp;220 }221 //cout<<"res2="<<res2<<endl;222 for(int i=cc-1;i>=1;i--)223 {224 bign tp=i;225 res3*=tp;226 }227 //cout<<"res3="<<res3<<endl;228 bign res=res1/res2;229 res/=res3;230 return res;231 }232 int main()233 {234 freopen("out.txt","w",stdout);235 cout<<"char list[55]={"<<"{\"1\"},"<<"{\"1\"},";236 int n;237 bign f[maxn];238 char ini1[5]="1",ini0[5]="0";239 f[0]=f[1]=f[2]=ini1;240 for(int i=3;i<=50;i++)241 {242 bign temp=ini0;243 for(int j=0;j<i-1;j++)244 {245 int x=(i-1-j)*(i-2-j)/2;246 bign ccc=c(i-1,j);247 temp+=f[1+j]*ccc*times2(x);248 }249 int x=i*(i-1)/2;250 f[i]=times2(x)-temp;251 cout<<"{\""<<f[i]<<"\"}";252 if(i==50) cout<<"}"<<endl;253 else cout<<",";254 }255 return 0;256 }
Poj1737
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。