hdu_3483A Very Simple Problem(C(m,n)+快速幂矩阵)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3483

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:

hdu_3483A Very Simple Problem(C(m,n)+快速幂矩阵)

 
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*109, 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
 
 //计算排列数(杨辉三角)
//C(m,n) = C(m-1,n-1)+C(m-1,n)
//快速幂
/*
* [题意]
* 输入n, x, m
* 求(1^x)*(x^1)+(2^x)*(x^2)+(3^x)*(x^3)+...+(n^x)*(x^n)
* [解题方法]
* 设f[n] = [x^n, n*(x^n), (n^2)*(x^n),..., (n^x)*(x^n)]
* 则f[n][k] = (n^k)*(x^n)
* 问题转化为求:( g[n] = f[1][x]+f[2][x]+...+f[n][x] )
* 设C(i,j)为组合数,即i种元素取j种的方法数
* 所以有:f[n+1][k] = ((n+1)^k)*(x^(n+1)) (二次多项式展开)
* = x*( C(k,0)*(x^n) +C(k,1)*n*(x^n)+...+C(k,k)*(n^k)*(x^n) )
* = x*( C(k,0)*f[n][0]+C(k,1)*f[n][1]+...+C(k,k)*f[n][k] )
* 所以得:
* |x*1 0................................0| |f[n][0]| |f[n+1][0]|
* |x*1 x*1 0............................0| |f[n][1]| |f[n+1][1]|
* |x*1 x*2 x*1 0........................0| * |f[n][2]| = |f[n+1][2]|
* |......................................| |.......| |.........|
* |x*1 x*C(k,1) x*C(k,2)...x*C(k,x) 0...0| |f[n][k]| |f[n+1][k]|
* |......................................| |.......| |.........|
* |x*1 x*C(x,1) x*C(x,2).......x*C(x,x) 0| |f[n][x]| |f[n+1][x]|
* |0................................0 1 1| |g[n-1] | | g[ n ] |
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
const ll maxn = ;
ll c[maxn][maxn];
ll n, mod, x, m;
struct Mat{
ll f[maxn][maxn];
};
void init()
{
ll i,j,k;
c[][] = c[][] = c[][] = ;
for(i = ; i < maxn; i++){
c[i][] = c[i][i] = ;
for(j = ; j < i; j++){
c[i][j] = c[i-][j]+c[i-][j-];
}
}
}
Mat operator *(Mat a, Mat b)
{
ll i, j, k;
Mat c;
memset(c.f,,sizeof(c.f));
for(k = ; k < m; k++){
for(i = ; i < m; i++){
for(j = ; j < m; j++){
if(!b.f[k][j]) continue;
c.f[i][j] = (c.f[i][j]+(a.f[i][k]*b.f[k][j])%mod)%mod;
}
}
}
return c;
}
Mat multi(Mat a,ll b)
{
Mat s;
memset(s.f,,sizeof(s.f));
for(int i = ; i < m; i++){
s.f[i][i] = ;
}
while(b){
if(b&) s = s*a;
a = a*a;
b>>=;
}
return s;
}
int main()
{
init();
while(~scanf("%lld%lld%lld",&n,&x,&mod))
{
if(n<&&x<&&mod<) break;
Mat e;
ll i, j;
ll ans = ;
memset(e.f,,sizeof(e.f));
for(i = ; i <= x; i++){
for(j = i; j <= x; j++){
e.f[j][i] = c[x-i][j-i]*x%mod;
}
}
e.f[][x+] = e.f[x+][x+] = ;
m = x+;
e = multi(e,n);
for(i = ; i < m-; i++) ans = (ans+x*e.f[i][m-])%mod;
printf("%lld\n",(ans+mod)%mod);
}
return ;
}
上一篇:关于IHttpModule的相关知识总结


下一篇:eclipse color theme 离线安装方法以及jar包