首页 > 代码库 > HDU 4427 Math Magic(三维dp)

HDU 4427 Math Magic(三维dp)

2024-08-04 02:57:39   217人阅读

题目大意：给你三个数n，m，k。表示有k个数，他们的和为n，k个数的最小公倍数是m。让你求出符合这个条件的k个数的序列有多少种。

一看以为是个数论题，还尝试这各种分解m，然后进行组合数求情况。但是组合出来的数没法做减法啊。。。

结果是道dp题目。i，j，k表示到了第i个数此时和为j，最小公倍数为k。已经有了多少种组合方法了，直接向后推就可以了啊。数组太大开不开啊，滚动一下就可以了啊。


Math Magic

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1321    Accepted Submission(s): 469


Problem Description
Yesterday, my teacher taught us about math: +, -, *, /, GCD, LCM... As you know, LCM (Least common multiple) of two positive numbers can be solved easily because of a * b = GCD (a, b) * LCM (a, b).
In class, I raised a new idea: “how to calculate the LCM of K numbers”. It‘s also an easy problem indeed, which only cost me 1 minute to solve it. I raised my hand and told teacher about my outstanding algorithm. Teacher just smiled and smiled...
After class, my teacher gave me a new problem and he wanted me solve it in 1 minute, too.
If we know three parameters N, M, K, and two equations:
1. SUM (A1, A2, ..., Ai, Ai+1,..., AK) = N
2. LCM (A1, A2, ..., Ai, Ai+1,..., AK) = M
Can you calculate how many kinds of solutions are there for Ai (Ai are all positive numbers).
I began to roll cold sweat but teacher just smiled and smiled. 
Can you solve this problem in 1 minute?
 

Input
There are multiple test cases.
Each test case contains three integers N, M, K. (1 <= N, M <= 1,000, 1 <= K <= 100)
 

Output
For each test case, output an integer indicating the number of solution modulo 1,000,000,007(109 + 7).
You can get more details in the sample and hint below.
 

Sample Input
4 2 2
3 2 2
 

Sample Output
1
2


Hint

The first test case: the only solution is (2, 2).
The second test case: the solution are (1, 2) and (2, 1).
 

Source
2012 Asia ChangChun Regional Contest
 
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <time.h>
#include <stack>
#include <map>
#include <set>
#define eps 1e-8
#define M 1000100
///#define LL long long
#define LL __int64
#define INF 0x3f3f3f
#define PI 3.1415926535898
#define mod 1000000007


using namespace std;

const int maxn = 1010;

int dp[2][maxn][maxn];
int lcm[maxn][maxn];
int num[maxn];


int LCM(int x, int y)
{
    return (x*y)/(__gcd(x, y));
}


void init()
{
    for(int i = 1; i <= 1000; i++)
        for(int j = 1; j <= 1000; j++) lcm[i][j] = LCM(i, j);
}


int main()
{
    int n, m, k;
    init();
    while(~scanf("%d %d %d", &n, &m, &k))
    {
        int ans = 0;
        for(int i = 1; i <= m; i++)
            if(!(m%i)) num[ans++] = i;
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < ans; j++) dp[0][i][num[j]] = 0;
        dp[0][0][1] = 1;
        int now = 0;
        for(int i = 1; i <= k; i++)
        {
            now ^= 1;
            for(int si = 0; si <= n; si++)
                for(int sj = 0; sj < ans; sj++) dp[now][si][num[sj]] = 0;
            for(int si = i-1; si <= n; si++)
            {
                for(int sj = 0; sj < ans; sj++)
                {
                    if(!dp[now^1][si][num[sj]]) continue;
                    for(int sx = 0; sx < ans; sx++)
                    {
                        int x = si+num[sx];
                        int y = lcm[num[sj]][num[sx]];
                        if(x > n || m%y) continue;
                        dp[now][x][y] += dp[now^1][si][num[sj]];
                        dp[now][x][y] %= mod;
                    }
                }
            }
        }
        printf("%d\n",dp[now][n][m]%mod);
    }
    return 0;
}


HDU 4427 Math Magic(三维dp)


联系
我们