首页 > ACM题库 > HDU-杭电 > HDU 3483-A Very Simple Problem-数论应用-[解题报告]HOJ
2014
04-04

HDU 3483-A Very Simple Problem-数论应用-[解题报告]HOJ

A Very Simple Problem

问题描述 :

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

Good Serial Inc.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

5050
444

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

题目大意:求sigma(X^k*k^X)%M,(1..k..N)。

解题思路:明显暴力会TLE,我们考虑相邻的两者的关系X^(k+1)*(k+1)^x = X*X^k*(k+1)^x,由于x很小,我们可以将(k+1)^X进行因式分解,这样我们可以得到一个转移关系,在通过增加一列可以进行求和。进行推导就可以将转移矩阵求出来,(这个比较难打,就不手打了,可以把这个用字母表示,更加有利于推导和理解)

通过代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define N 60
#define ll long long
using namespace std;
ll a[N][N];
ll b[N][N];
ll c[N][N];
ll tp[N][N];
//void print(ll pt[N][N],int nb){
//    for (int i=0;i<=nb+1;i++){
//        for (int j=0;j<=nb+1;j++)
//            printf("%I64d ",pt[i][j]);
//        printf("\n");
//    }
//}
int main(){
    int n,x;
    ll MOD;
    while (scanf("%d%d",&n,&x)==2){
        cin>>MOD;
        if (n<0&&x<0&&MOD<0) break;
        for (int i=0;i<=x;i++)
            c[i][i]=c[i][0]=1ll;
        for (int i=2;i<=x;i++)
            for (int j=1;j<i;j++)
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for (int i=0;i<=x;i++)
            for (int j=0;j<=i;j++)
                a[j][i]=c[i][j]*x%MOD;
        for (int i=0;i<=x;i++)
            a[i][x+1]=a[i][x];
        a[x+1][x+1]=1ll;
        for (int i=0;i<=x+1;i++)
            b[0][i]=x;
        n=n-1;
        while (n>0){
            if (n%2){
                memset(tp,0,sizeof(tp));
                for (int i=0;i<=x+1;i++)
                    for (int j=0;j<=x+1;j++)
                        for (int k=0;k<=x+1;k++)
                            tp[i][j]=(tp[i][j]+b[i][k]*a[k][j])%MOD;
                memcpy(b,tp,sizeof(tp));
            }
            n=n/2;
            memset(tp,0,sizeof(tp));
            for (int i=0;i<=x+1;i++)
                for (int j=0;j<=x+1;j++)
                    for (int k=0;k<=x+1;k++)
                        tp[i][j]=(tp[i][j]+a[i][k]*a[k][j])%MOD;
            memcpy(a,tp,sizeof(tp));
        }
        cout<<b[0][x+1]<<endl;
    }
    return 0;
}

参考:http://blog.csdn.net/ruptins/article/details/21420125


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?