hdu 4427 Math Magic(DP, 레벨 4)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Practice
HDU 4427
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 (A
1, A
2, ..., A
i, A
i+1,..., A
K) = N
2. LCM (A
1, A
2, ..., A
i, A
i+1,..., A
K) = M
Can you calculate how many kinds of solutions are there for A
i (A
i 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(10
9 + 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).
사고방식: dp[K][N][M];K, 및 LCM
dp[K][N][M]=sum(dp[K-1][N-x][y]);LCM(x,y)=M;
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
using namespace std;
const int mm=1002;
const int mod=1e9+7;
int LCM[mm][mm];
int dp[2][mm][mm],ppp[mm],pos;
int gcd(int a,int b)
{ int c;
while(b)
{
c=b;b=a%b;a=c;
}
return a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
int main()
{
FOR(i,1,mm-1)FOR(j,1,mm-1)
LCM[i][j]=lcm(i,j);
int N,M,K;///dp num sum LCM
while(~scanf("%d%d%d",&N,&M,&K))
{
pos=0;
FOR(i,1,M)
if(M%i==0)
ppp[pos++]=i;
int now=0;
FOR(i,0,N)FOR(j,0,pos-1)
dp[now][i][ ppp[j] ]=0;
dp[now][0][1]=1;
FOR(i,1,K)///K
{
now^=1;
FOR(j,0,N)FOR(k,0,pos-1)
dp[now][j][ ppp[k] ]=0;///clear dp
FOR(j,i-1,N)/// 1
FOR(k,0,pos-1)
{
if(dp[now^1][j][ ppp[k] ]==0)continue;
FOR(p,0,pos-1)/// p
{
int x=j+ppp[p];
int y=LCM[ ppp[p] ][ ppp[k] ];
if(x>N||M%y!=0)continue;
dp[now][x][y]+=dp[now^1][j][ ppp[k] ];
if(dp[now][x][y]>=mod)
dp[now][x][y]-=mod;
}
}
}
printf("%d
",dp[now][N][M]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.