[hihoCoder] #1096 : Divided Product

时间限制:10000ms单点时限:1000ms内存限制:256MB

描述

Given two positive integers N and M, please divide N into several integers A1, A2, …, Ak (k >= 1), so that:

1. 0 < A1 < A2 < … < Ak;

2. A1 + A2 + … + Ak = N;

3. A1, A2, …, Ak are different with each other;

4. The product of them P = A1 * A2 * … * Ak is a multiple of M;

How many different ways can you achieve this goal?

输入

Two integers N and M. 1 <= N <= 100, 1 <= M <= 50.

输出

Output one integer — the number of different ways to achieve this goal, module 1,000,000,007.

样例提示

There are 4 different ways to achieve this goal for the sample:

A1=1, A2=2, A3=4;

A1=1, A2=6;

A1=2, A2=5;

A1=3, A2=4.

样例输入

7 2

样例输出

4

说好的这题是动规呢？想了半天动规没想出来，写了个DFS，然后居然通过了。有空再想想。

 #include <iostream>
 #include <vector>
 #include <algorithm>
 using namespace std; typedef long long ll;
 const ll MOD = ; int N, M; void dfs(ll &res, ll idx, ll sum, ll pro) {
     if (sum == N) {
         if (pro % M == ) ++res;
         return;
     }
     for (int i = idx + ; i <= N - sum; ++i) {
         dfs(res, i, sum + i, pro * i);
     }
 } void solve() {
     ll res = ;
     dfs(res, , , );
     cout << res << endl;
 } int main() {
     while (cin >> N >> M) {
         solve();
     }
 }