A Very Simple Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 945 Accepted Submission(s): 471

Problem Description

This is a very simple problem. Given three integers N, x, and M, your task is to calculate out the following value:

Input

There are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*10⁹, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.

Output

For each test case, print a line with an integer indicating the result.

Sample Input

100 1 10000 3 4 1000 -1 -1 -1

Sample Output

5050 444

Source

2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU

  1 //计算排列数（杨辉三角）
  2 //C(m,n) = C(m-1,n-1)+C(m-1,n)
  3 //快速幂
  4 /*
  5 *  [题意]
  6 *   输入n, x, m
  7 *   求(1^x)*(x^1)+(2^x)*(x^2)+(3^x)*(x^3)+...+(n^x)*(x^n)
  8 *  [解题方法]
  9 *   设f[n] = [x^n, n*(x^n), (n^2)*(x^n),..., (n^x)*(x^n)]
 10 *   则f[n][k] = (n^k)*(x^n)
 11 *   问题转化为求：( g[n] = f[1][x]+f[2][x]+...+f[n][x] )
 12 *   设C(i,j)为组合数，即i种元素取j种的方法数
 13 *   所以有：f[n+1][k] = ((n+1)^k)*(x^(n+1)) （二次多项式展开）
 14 *                     = x*( C(k,0)*(x^n)  +C(k,1)*n*(x^n)+...+C(k,k)*(n^k)*(x^n) )
 15 *                     = x*( C(k,0)*f[n][0]+C(k,1)*f[n][1]+...+C(k,k)*f[n][k] )
 16 *   所以得：
 17 *   |x*1 0................................0|        |f[n][0]|       |f[n+1][0]|
 18 *   |x*1 x*1 0............................0|        |f[n][1]|       |f[n+1][1]|
 19 *   |x*1 x*2 x*1 0........................0|    *   |f[n][2]|   =   |f[n+1][2]|
 20 *   |......................................|        |.......|       |.........|
 21 *   |x*1 x*C(k,1) x*C(k,2)...x*C(k,x) 0...0|        |f[n][k]|       |f[n+1][k]|
 22 *   |......................................|        |.......|       |.........|
 23 *   |x*1 x*C(x,1) x*C(x,2).......x*C(x,x) 0|        |f[n][x]|       |f[n+1][x]|
 24 *   |0................................0 1 1|        |g[n-1] |       | g[ n ]  |
 25 */
 26 #include<cstdio>
 27 #include<cstring>
 28 #include<cmath>
 29 #include<algorithm>
 30 using namespace std;
 31 #define ll long long
 32 const ll maxn = 55;
 33 ll c[maxn][maxn];
 34 ll n, mod, x, m;
 35 struct Mat{
 36     ll f[maxn][maxn];
 37 };
 38 void init()
 39 {
 40     ll i,j,k;
 41     c[0][0] = c[1][0] = c[1][1] = 1;
 42     for(i = 2; i < maxn; i++){
 43         c[i][0] = c[i][i] = 1;
 44         for(j = 1; j < i; j++){
 45             c[i][j] = c[i-1][j]+c[i-1][j-1];
 46         }
 47     }
 48 }
 49 Mat operator *(Mat a, Mat b)
 50 {
 51     ll i, j, k;
 52     Mat c;
 53     memset(c.f,0,sizeof(c.f));
 54     for(k = 0; k < m; k++){
 55         for(i = 0; i < m; i++){
 56             for(j = 0; j < m; j++){
 57                 if(!b.f[k][j]) continue;
 58                 c.f[i][j] = (c.f[i][j]+(a.f[i][k]*b.f[k][j])%mod)%mod;
 59             }
 60         }
 61     }
 62     return c;
 63 }
 64 Mat multi(Mat a,ll b)
 65 {
 66     Mat s;
 67     memset(s.f,0,sizeof(s.f));
 68     for(int i = 0; i < m; i++){
 69         s.f[i][i] = 1;
 70     }
 71     while(b){
 72         if(b&1) s = s*a;
 73         a = a*a;
 74         b>>=1;
 75     }
 76     return s;
 77 }
 78 int main()
 79 {
 80     init();
 81     while(~scanf("%lld%lld%lld",&n,&x,&mod))
 82     {
 83         if(n<0&&x<0&&mod<0) break;
 84         Mat e;
 85         ll i, j;
 86         ll ans = 0;
 87         memset(e.f,0,sizeof(e.f));
 88         for(i = 0; i <= x; i++){
 89             for(j = i; j <= x; j++){
 90                 e.f[j][i] = c[x-i][j-i]*x%mod;
 91             }
 92         }
 93         e.f[0][x+1] = e.f[x+1][x+1] = 1;
 94         m = x+2;
 95         e = multi(e,n);
 96         for(i = 0; i < m-1; i++) ans = (ans+x*e.f[i][m-1])%mod;
 97         printf("%lld
",(ans+mod)%mod);
 98     }
 99     return 0;
100 }