学步园

题目大意：给你一个集合S，里面全部是3的n次方。

现在需要假设从中抽出一部分出来构成子集和X，X中各个元素的和为w，现在要求把所有的X集合按w来排序，输入n，输出第n个集合

X集合明显有无穷多个。

解题思路：

题目数据量非常大，是10^18次方。所以只能构思时间复杂度在O(logn)以下的算法。

我们可以想象一下对于3^x以下的所有S中的集合元素总共可以构成多少个X集合？

答案：C(X,0)+C(X,1)+C(X,2)+C(X,3)+....+C(X,X)=2^X个。

仔细思考下可以发现这个答案和n的二进制码有关。

/*详细过程不方便文字叙述*/

方法就是把n-1进行二进制分解，然后依次输出所对应的3的x次方。

我的代码：

#include<stdio.h><br /> #include<string.h></p> <p>char str[101][100]={<br /> {"1"},<br /> {"3"},<br /> {"9"},<br /> {"27"},<br /> {"81"},<br /> {"243"},<br /> {"729"},<br /> {"2187"},<br /> {"6561"},<br /> {"19683"},<br /> {"59049"},<br /> {"177147"},<br /> {"531441"},<br /> {"1594323"},<br /> {"4782969"},<br /> {"14348907"},<br /> {"43046721"},<br /> {"129140163"},<br /> {"387420489"},<br /> {"1162261467"},<br /> {"3486784401"},<br /> {"10460353203"},<br /> {"31381059609"},<br /> {"94143178827"},<br /> {"282429536481"},<br /> {"847288609443"},<br /> {"2541865828329"},<br /> {"7625597484987"},<br /> {"22876792454961"},<br /> {"68630377364883"},<br /> {"205891132094649"},<br /> {"617673396283947"},<br /> {"1853020188851841"},<br /> {"5559060566555523"},<br /> {"16677181699666569"},<br /> {"50031545098999707"},<br /> {"150094635296999121"},<br /> {"450283905890997363"},<br /> {"1350851717672992089"},<br /> {"4052555153018976267"},<br /> {"12157665459056928801"},<br /> {"36472996377170786403"},<br /> {"109418989131512359209"},<br /> {"328256967394537077627"},<br /> {"984770902183611232881"},<br /> {"2954312706550833698643"},<br /> {"8862938119652501095929"},<br /> {"26588814358957503287787"},<br /> {"79766443076872509863361"},<br /> {"239299329230617529590083"},<br /> {"717897987691852588770249"},<br /> {"2153693963075557766310747"},<br /> {"6461081889226673298932241"},<br /> {"19383245667680019896796723"},<br /> {"58149737003040059690390169"},<br /> {"174449211009120179071170507"},<br /> {"523347633027360537213511521"},<br /> {"1570042899082081611640534563"},<br /> {"4710128697246244834921603689"},<br /> {"14130386091738734504764811067"},<br /> {"42391158275216203514294433201"},<br /> {"127173474825648610542883299603"},<br /> {"381520424476945831628649898809"},<br /> {"1144561273430837494885949696427"},<br /> {"3433683820292512484657849089281"},<br /> {"10301051460877537453973547267843"},<br /> {"30903154382632612361920641803529"},<br /> {"92709463147897837085761925410587"},<br /> {"278128389443693511257285776231761"},<br /> {"834385168331080533771857328695283"},<br /> {"2503155504993241601315571986085849"},<br /> {"7509466514979724803946715958257547"},<br /> {"22528399544939174411840147874772641"},<br /> {"67585198634817523235520443624317923"},<br /> {"202755595904452569706561330872953769"},<br /> {"608266787713357709119683992618861307"},<br /> {"1824800363140073127359051977856583921"},<br /> {"5474401089420219382077155933569751763"},<br /> {"16423203268260658146231467800709255289"},<br /> {"49269609804781974438694403402127765867"},<br /> {"147808829414345923316083210206383297601"},<br /> {"443426488243037769948249630619149892803"},<br /> {"1330279464729113309844748891857449678409"},<br /> {"3990838394187339929534246675572349035227"},<br /> {"11972515182562019788602740026717047105681"},<br /> {"35917545547686059365808220080151141317043"},<br /> {"107752636643058178097424660240453423951129"},<br /> {"323257909929174534292273980721360271853387"},<br /> {"969773729787523602876821942164080815560161"},<br /> {"2909321189362570808630465826492242446680483"},<br /> {"8727963568087712425891397479476727340041449"},<br /> {"26183890704263137277674192438430182020124347"},<br /> {"78551672112789411833022577315290546060373041"},<br /> {"235655016338368235499067731945871638181119123"},<br /> {"706965049015104706497203195837614914543357369"},<br /> {"2120895147045314119491609587512844743630072107"},<br /> {"6362685441135942358474828762538534230890216321"},<br /> {"19088056323407827075424486287615602692670648963"},<br /> {"57264168970223481226273458862846808078011946889"},<br /> {"171792506910670443678820376588540424234035840667"},<br /> {"515377520732011331036461129765621272702107522001"}<br /> };//这张表已经达到大数的水平了，而且对于超级大的n肯定有的集合元素已经是大数了，所以我是用java打的表。</p> <p>int main()<br /> {<br /> long long n,ans[300],num,i,l;<br /> char out[101][100];<br /> bool flag;<br /> while(scanf("%lld",&n)!=EOF)<br /> {<br /> if(n==0)<br /> break;<br /> n=n-1;<br /> num=0,flag=true,l=0;<br /> while(n)<br /> {<br /> num++;<br /> ans[num]=n%2;<br /> n=n/2;<br /> }<br /> for(i=1;i<=num;i++)<br /> {<br /> if(ans[i])<br /> {<br /> flag=false;<br /> l++;<br /> strcpy(out[l],str[i-1]);<br /> }<br /> }<br /> if(flag)<br /> printf("{ }/n");<br /> else<br /> {<br /> printf("{");<br /> for(i=1;i<=l-1;i++)<br /> printf(" %s,",out[i]);<br /> printf(" %s }/n",out[l]);<br /> }<br /> }<br /> return 0;<br /> }<br />