vb 导出整数科学计数法_可整数组的计数

绝地灬酷狼 2023-03-05 09:49 16阅读 0赞

vb 导出整数 科学计数法

**Problem statement:**

**问题陈述：**

Given two positive integer ***n*** and ***m***, find how many arrays of size ***n*** that can be formed such that:

给定两个正整数***n***和***m*** ，找出可以形成多少个大小为***n的***数组：

1.  Each element of the array is in the range ***\[1, m\]***
    
    数组的每个元素都在***\[1，m\]***范围内
2.  Any *adjacent element pair is divisible*, i.e., that one of them divides another. Either element ***A\[i\]*** divides ***A\[i + 1\]*** or ***A\[i + 1\]*** divides ***A\[i\]***.
    
    任何*相邻的元素对都是可分割的* ，即，其中一个*元素对*另一个*元素* 。 元素***A \[i\]***除以***A \[i + 1\]***或***A \[i + 1\]***除以***A \[i\]*** 。

**Input:**

**输入：**

Only one line with two integer, ***n*** & ***m*** respectively.

只有一行包含两个整数，分别为***n***和***m*** 。

**Output:**

**输出：**

Print number of different possible ways to create the array. Since the output could be long take modulo **10^9+7**.

打印创建数组的各种可能方式的数量。 由于输出可能很长，取模**10 ^ 9 + 7** 。

**Constraints:**

**限制条件：**

1<=n, m<=100

**Example:**

**例：**

Input: 
        n = 3, m = 2.
        
        Output: 
        8
        
        Explanation:
        {1,1,1},{1, 1, 2}, {1, 2, 1}, 
        {1, 2, 2}, {2, 1, 1},
        {2,1,2},  {2,2,1}, {2,2,2} are possible arrays.
    
        Input: 
        n = 1, m = 5.
        
        Output: 
        5
        Explanation:
        {1}, {2}, {3}, {4}, {5}

**Solution Approach:**

**解决方法：**

The above problem is a great example of recursion. What can be the recursive function and how we can formulate.

上面的问题是递归的一个很好的例子。 什么是递归函数，以及我们如何公式化。

Say,

说，

Let

让

**F(n, m) **= number of ways for array size n and range 1 to m

**F(n，m)** =数组大小为n且范围为1到m的路径数

Now,

现在，

We actually can try picking every element from raging ***1*** to ***m*** and try recurring for other elements

实际上，我们可以尝试从***1***到***m***范围内选取每个元素，然后尝试对其他元素进行重复

So, the function can be written like:

因此，该函数可以这样写：

Function: NumberofWays(cur_index,lastelement,n,m)

So, to describe the arguments,

因此，为了描述这些论点，

*cur\_index* is your current index and the last element is the previous index value assigned. So basically need to check which value with range 1 to *m* fits in the *cur\_index* such that the divisibility constraint satisfies.

*cur\_index*是当前索引，最后一个元素是分配的前一个索引值。 因此，基本上需要检查范围在1到*m之间的*哪个值适合*cur\_index* ，以便除数约束满足。

So, to describe the body of the function

因此，要描述功能的主体

Function NumberofWays(cur_index,lastelement,n,m)    
        // formed the array completely
        if(cur_index==n)
            return 1;
        sum=0
        
        // any element in the range
        for j=1 to m 
            // if divisible then lastelement,
            // j can be adjacent pair
            if(j%lastelement==0 || lastelement%j==0)
                // recur for rest of the elments
                sum=(sum%MOD+ NumberofWays(cur_index+1,j,n,m)%MOD)%MOD; 
            end if
        end for
    End function

Now the above recursive function generates many overlapping sub-problem and that's why we use the top-down DP approach to store already computed sub-problem results.  
Below is the implementation with adding memoization.

现在，上面的递归函数会生成许多重叠的子问题，这就是为什么我们使用自上而下的DP方法来存储已经计算出的子问题结果的原因。  
下面是添加备忘录的实现。

Initiate a 2D DP array with -1

使用-1启动2D DP阵列

Function NumberofWays(cur_index,lastelement,n,m)
        // formed the array completely
        if(cur_index==n)
            return 1;
        // if solution to sub problem already exits
        if(dp[cur_index][lastelement]!=-1) 
            return dpdp[cur_index][lastelement];    
        sum=0
        for j=1 to m // any element in the range
            // if divisible then lastelement,j can be adjacent pair
            if(j%lastelement==0 || lastelement%j==0)
                // recur for rest of the elments
                sum=(sum%MOD+ NumberofWays(cur_index+1,j,n,m)%MOD)%MOD; 
            end if
        end for
        Dp[curindex][lastelement]=sum
        Return Dp[curindex][lastelement] 
    End function

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    #define MOD 1000000007
    
    int dp[101][101];
    
    int countarray(int index, int i, int n, int m)
    {
        // if solution to sub problem already exits
        if (dp[index][i] != -1)
            return dp[index][i];
    
        if (index == n)
            return 1;
        int sum = 0;
    
        //any element in the range
        for (int j = 1; j <= m; j++) {
            // if divisible then i,j can be adjacent pair
            if (j % i == 0 || i % j == 0) {
                // recur for rest of the elments
                sum = (sum % MOD + countarray(index + 1, j, n, m) % MOD) % MOD;
            }
        }
        dp[index][i] = sum;
        return dp[index][i];
    }
    
    int main()
    {
        int n, m;
    
        cout << "Enter value of n:\n";
        cin >> n;
        cout << "Enter value of m:\n";
        cin >> m;
    
        // initialize DP matrix
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = -1;
            }
        }
    
        cout << "number of ways are: " << countarray(0, 1, n, m) << endl;
    
        return 0;
    }

**Output:**

**输出：**

Enter value of n:
    3
    Enter value of m:
    2
    number of ways are: 8

> 翻译自: [https://www.includehelp.com/icp/count-of-divisible-array.aspx][https_www.includehelp.com_icp_count-of-divisible-array.aspx]

vb 导出整数 科学计数法

[https_www.includehelp.com_icp_count-of-divisible-array.aspx]: https://www.includehelp.com/icp/count-of-divisible-array.aspx