思路：动态规划题

给出n和m的值，要求求出一个"特别数组"的数量，并对1e9+7取模

其实并没有什么其他好计算的办法，那么就想到动态规划能否解决问题，首先n和m的范围都在1000以内，那么代表支持$O(n^2logn)$的时间复杂度，那么dp的第一维肯定是我们有多少个数，另外"特别数组"是所有数加起来是n的倍数，也就是说模n为0，那么第二维就可以设置成当前所有数加起来模n为多少

所以我们设dp[i][j]，表示当前一共有i个数并且所有数加起来模n为j的数组的数量，那么在转移的时候可以枚举i与j和当前最后一个数是多少，最后一位数一定是i的倍数，所以我们可以用一个调和级数的时间复杂度去枚举它，最后答案即为dp[n][0]

转移方程为

        for(int i=1;i<=n;i++){
            for(int j=0;j<n;j++){//模n最大为n-1
                for(int k=i;k<=m;k+=i){//k表示最后一个数为多少，它一定是i的倍数
                    dp[i][j] += dp[i-1][(j-k%n+n)%n];//若前i-1个数模n为(j-k+n)%n,那么((j-k+n)%n+k)%n=j,枚举所有情况
                    dp[i][j] %= mod;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<n;j++)//模n最大为n-1
            {
                for(int p=i;p<=m;p+=i)//p表示最后一个数为多少，它一定是i的倍数
                {
                    dp[i][j]=(dp[i][j]+dp[i-1][(j-p%n+n)%n])%mod;//若前i-1个数模n为(j-p+n)%n,那么((j-p+n)%n+p)%n=j,枚举所有情况
                }
            }
        }

时间复杂度为$O(n^2logm)$

代码

C++

AC

#include <iostream>
using namespace std;

const int mod = 1000000007;
long long dp[1100][1100];

int main() {
    int n, m;
    cin >> n >> m;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            for (int p = i; p <= m; p += i) {
                dp[i][j] = (dp[i][j] + dp[i - 1][(j - p % n + n) % n]) % mod;
            }
        }
    }
    cout << dp[n][0] << endl;
    return 0;
}

python

mod = 1000000007
dp = [[0 for _ in range(1100)] for _ in range(1100)]

n, m = map(int, input().split())
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(n):
        for p in range(i, m + 1, i):
            dp[i][j] = (dp[i][j] + dp[i - 1][(j - p % n + n) % n]) % mod

print(dp[n][0])

Java

import java.util.*;
class Main {
    static int n,m;
    static long mod=1000000007;
    static long[][] dp = new long[1100][1100];
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int p=i;p<=m;p+=i)
                {
                    dp[i][j]=(dp[i][j]+dp[i-1][(j-p%n+n)%n])%mod;
                }
            }
        }
        System.out.println(dp[n][0]);
    }
}

题目描述

小红最近一直在学习数组，突然有了一个想法，他定义了一个“特别数组”，当且仅当满足以下三个条件:

1. 对于$1 \leq i \leq n，有1 \leq a_i \leq m$
2. 对于$1 \leq i \leq n$保证$a_i$是$i$的倍数。
3. $a_1+a_2+....+a_n$是$n$的倍数。

现在给出$n$和$m$的值，请你求出满足条件的“特别数组”数量。由于答案可能过大，请对$10^9+ 7$取模。

输入描述

两个正整数$n$和$m$，用空格隔开。

$1 \leq n,m \leq 1000$

输出描述

特别数组的数量，答案对$10^9+ 7$取模。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3 5

输出

4

说明

$[1,2,3],[4,2,3],[2,4,3],[5,4,3]$共有以上四个好数组