HDU 5793 A Boring Question ——（找规律，快速幂 + 求逆元）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

参考博客：http://www.cnblogs.com/Sunshine-tcf/p/5737627.html。

说实话，官方博客的推导公式看不懂。。。只能按照别人一样打表找规律了。。。但是打表以后其实也不是很好看出规律的。。。而且这个表都写了半天233。。。（真是太弱了= =）为了打表，我们应当先知道k数列必须是不递减的才能满足值不为0，因此我们可以用递归来写这个表（类似于dfs）。

AC代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 typedef long long ll;

 const int mod = ;

 int qpow(int a,int b)

 {

     int ans = ;

     while(b)

     {

         if(b & ) ans = 1LL * ans * a % mod;

         b >>= ;

         a = 1LL * a * a % mod;

     }

     return ans;

 }

 int inv(int p)

 {

     return qpow(p,mod-);

 }

 int main()

 {

     int T;scanf("%d",&T);

     while(T--)

     {

         int n,m;scanf("%d%d",&n,&m);

         int ans = qpow(m,n+);

         ans = ((ans - ) % mod + mod) % mod;

         ans = 1LL * ans * inv(m-) % mod;

         printf("%d\n",ans);

     }

 }

打表代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 int c[][];

 //int n,m;

 void init()

 {

     c[][] = c[][] = c[][] = ;

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

     {

         c[i][] = c[i][i] = ;

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

         {

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

         }

     }

 }

 int ans = ,a[];

 void solve(int pos,int now,int n,int m)

 {

     a[pos] = now;

     if(pos == m)

     {

         int t = ;

         for(int i=;i<=m;i++) t *= c[a[i]][a[i-]];

         ans += t;

         return;

     }

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

     {

         solve(pos+,i,n,m);

     }

 }

 void getAns(int n,int m)

 {

     memset(a,,sizeof(a));

     ans = ;

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

     {

         solve(,i,n,m);

     }

 }

 int main()

 {

     init();

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

     {

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

         {

             getAns(i,j);

             printf("f(%d,%d)=%d  ",i,j,ans);

         }

         puts("");

     }

     /*while(scanf("%d%d",&n,&m)==2)

     {

         memset(a,0,sizeof(a));

         ans = 0;

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

         {

             solve(1,i);

         }

         printf("%d\n",ans);

     }*/

 }