`

HDU 3483 A Very Simple Problem

阅读更多
/*
*  [题意]
*   输入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 <iostream>
#include <cstring>
using namespace std;
#define M 55
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)

int ans[M], mod, C[M][M];
int ret[M][M], init[M][M];

void ini(int n, int x)
{
    memset(init, 0, sizeof(init));
    FF(i, n) FF(j, i+1)
        init[i][j] = (LL)x*C[i][j] % mod;
    FF(i, n) ans[i] = x;
    ans[n] = 0;
    init[n][n-1] = init[n][n] = 1;
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    int tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + (LL)a[j]*b[i][j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int main()
{
    int i, j, n, x;
    while (cin >> n >> x >> mod, n >= 1)
    {
        for(i = 0; i <= x; i++)
            C[i][0] = C[i][i] = 1;
        for(i = 2; i <= x; i++)
            for(j = 1; j < i; j++)
                C[i][j] = ((LL)C[i-1][j-1]+C[i-1][j]) % mod;
        ini(x+1, x);
        qmod(x+2, n);
        matmul(ans, ret, x+2);
        cout << ans[x+1] << endl;
    }
    return 0;
}

 

1
4
分享到:
评论

相关推荐

    HDU 1022 Train Problem I 附详细思路

    HDU 1022 Train Problem I 附详细思路

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo.zip

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    hdu-api:A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API 的 SDK

    A simple SDK for HDU. hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    - 这个函数接收两个字符串参数`a`和`b`,代表两个待相加的大整数,以及一个整数`fn`作为结果存放的位置索引。 - 函数内部首先计算两个数的长度,然后进行逐位相加,同时考虑进位的情况。 - 结果存储在一个临时的`...

    hdu 1753 大明A+B

    Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...

    HDU1059的代码

    HDU1059的代码

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    hdu1001解题报告

    hdu1001解题报告

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    HDU1019(2028)解题报告

    The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

Global site tag (gtag.js) - Google Analytics