【穷竭】POJ3187-Backward Digit Sums

【思路】

利用杨辉三角形，每一个数字被加的次数等于它在杨辉三角形中对应的那个数字。注意这道题的意思是，最底层是N的全排序，而不是指1..10都可以。生成杨辉三角形的时候第一次我用了二重循环模拟生成，后来学习到，杨辉三角形中，第n行第k个数字为C。不过在第二个程序中我的杨辉三角形没有预处理，导致了很多时间的浪费。用了深搜和STL两种方法。深搜因为能够剪枝所以明显要比Next_permuation快。

 /*232K    0MS*/

 /*模拟+深搜*/

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int MAXN=+;

 int n,sum;

 int a[MAXN][MAXN];

 int ans[MAXN];

 int vis[MAXN];

 int f;

 void gettri()

 {

     for (int i=;i<n;i++)

     {

         a[i][]=;

         a[i][i]=;

     }

     for (int i=;i<n;i++)

         for (int j=;j<i;j++)

             a[i][j]=a[i-][j-]+a[i-][j];

 }

 void print()

 {

     for (int i=;i<n;i++) cout<<ans[i]<<' ';

     cout<<endl;

 }

 void getnum(int step,int nowsum)

 {

     if (step==n)

     {

         if (nowsum==sum)

         {

             f=;

             printf();

         }

         return;

     }

     if (f||nowsum>sum) return;

     for (int i=;i<=n;i++)

     {

         if (vis[i]==) continue;

         vis[i]=;

         ans[step]=i;

         getnum(step+,nowsum+i*a[n-][step]);

         vis[i]=;

     }

 }

 int main()

 {

     scanf("%d%d",&n,&sum);

     gettri();

     memset(vis,,sizeof(vis));

     f=;

     getnum(,);

     return ;

 }

 /*232K    469MS*/

 /*组合+STL*/

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=+;

 int n,sum;

 int ans[MAXN];

 int c(int n,int k)

 {

     int cresult=;

     for (int i=;i<k;i++) cresult=cresult*(n-i)/(i+);

     //这里不能写成cresult=cresult*(n-i)/(k-i)，因为如果从大到小可能无法整除，精确度会导致错误

     return cresult;

 }

 int main()

 {

     scanf("%d%d",&n,&sum);

     for (int i=;i<n;i++) ans[i]=i+;

     do

     {

         int result=;

         for (int i=;i<n;i++) result+=ans[i]*c(n-,i);

         if (result==sum)

         {

             for (int i=;i<n;i++) cout<<ans[i]<<' ';

             cout<<endl;

             break;

         }

     }while (next_permutation(ans,ans+n));

     return ;

 }