递推

P1713升级版。

题目从连续子序列变成了子序列，也就是说我们需要求出所有子序列的和$mod 15$及$mod 60$的个数。

我们假设枚举到第$i$个数时，我们已经知道前$i-1$个数的子序列的所有和取模的情况，那么该如何计算加入第$i$个数的情况呢？

定义$f15[i][j]$表示前$i$个数的所有子序列和中$mod15=j$的个数。

1. 不加入当前数$a_i$，则有$f15[i][j]=f15[i-1][j]$
2. 加入当前数$a_i$，那么有$f15[i][(j+a_i)mod15]=f15[i-1][j]$

即，如果加入当前数$a_i$，那么前$i-1$所有模为$j$的情况都会变成$(j+a_i)mod15$的情况。

因此，这是一个递推的过程。

时间复杂度为$O(60N)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 1e9+7;
const int maxn=1e5+10;
int n;
ll f15[maxn][16],f60[maxn][61];
int nums[maxn];
ll ans=0;

void solve() {
    // 初始存在和为0的哈希值
    f15[0][0]=1;
    f60[0][0]=1;
    for (int i = 1; i <= n; i++) {
		for(int j=0;j<15;++j){
			f15[i][j] += f15[i-1][j];
			f15[i][j]%=mod;
			f15[i][(j+nums[i])%15] += f15[i-1][j];
			f15[i][(j+nums[i])%15]%=mod;
		}
		for(int j=0;j<60;++j){
			f60[i][j] += f60[i-1][j];
			f60[i][j]%=mod;
			f60[i][(j+nums[i])%60] += f60[i-1][j];
			f60[i][(j+nums[i])%60]%=mod;
		}
    }
    ans = (f15[n][0]-f60[n][0]+mod)%mod;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
    	scanf("%d",&nums[i]);
	}
    solve();
    cout<<ans;
    
    return 0;
}

java

import java.util.Scanner;

public class Main {
    private static final long MOD = 1000000007L;
    private static final int MAXN = 100010;
    private static int n;
    private static long[][] f15 = new long[MAXN][16];
    private static long[][] f60 = new long[MAXN][61];
    private static int[] nums = new int[MAXN];
    private static long ans = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入处理
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            nums[i] = scanner.nextInt();
        }

        solve();

        System.out.println(ans);
        scanner.close();
    }

    private static void solve() {
        // 初始存在和为0的哈希值
        f15[0][0] = 1;
        f60[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 15; j++) {
                f15[i][j] = (f15[i][j] + f15[i - 1][j]) % MOD;
                f15[i][(j + nums[i]) % 15] = (f15[i][(j + nums[i]) % 15] + f15[i - 1][j]) % MOD;
            }
            for (int j = 0; j < 60; j++) {
                f60[i][j] = (f60[i][j] + f60[i - 1][j]) % MOD;
                f60[i][(j + nums[i]) % 60] = (f60[i][(j + nums[i]) % 60] + f60[i - 1][j]) % MOD;
            }
        }

        ans = (f15[n][0] - f60[n][0] + MOD) % MOD;
    }
}

python

n = int(input())
nums = list(map(int, input().split()))

def sub_sequence_dp(nums):
    n = len(nums)
    MOD = int(1e9) + 7
    # dp[i][j]表示nums[:i]中有多少个子序列的和 % 60 == j
    dp = [[0] * 60 for _ in range(n + 1)]
    for i in range(1, n + 1):
        r = nums[i - 1] % 60
        for j in range(60):
            dp[i][j] = (dp[i-1][j] + dp[i-1][(j-r) % 60]) % MOD
            if j == r:
                dp[i][j] = (1 + dp[i][j]) % MOD
    return (dp[n][15] + dp[n][30] + dp[n][45]) % MOD

print(sub_sequence_dp(nums))

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小红非常喜欢一部 2023 年上线的作品，但是这部作品到 2025年才能有第二季，小红觉得这个 2024 年不需要了，想直接结束2024年，因此她现在，常喜欢3和5但不喜欢4。 现在小红有一个数组，她想知道这个数组中有多少个子序列的和是3和5的倍数，但不是4的倍数。

由于这个答案可能很大，因此你需要输一答案对$10^9+7$取模后的结果。

输入描述

第一行输入一个整数$n(1\le n \le 10^5)$表示数组长度。

第二行输入$n$个整数$a(1\le a_i\le 10^9)$表示数组

输出描述

输出一个整数表示答案

样例

输入

3
13 30 17

输出

2

说明

有两个子序列满足要求:[13,17],[30]。