QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#713998#7128. Huge productshejinming983282TL 0ms3976kbC++231.3kb2024-11-05 21:12:362024-11-05 21:12:36

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 21:12:36]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3976kb
  • [2024-11-05 21:12:36]
  • 提交

answer

#include <iostream>
#include <set>
#include <cmath>
#include <iterator>

const int MOD = 1000000007;

int main() {
    // Read the input values
    long long a[10];
    for (int i = 0; i < 10; i++) {
        std::cin >> a[i];
    }

    // Initialize dp set to track possible products
    std::set<long long> dp;
    dp.insert(1); // The product 1 is always possible (by picking no numbers)

    // Process each number from 1 to 10
    for (int i = 0; i < 10; i++) {
        long long num = i + 1; // The number we are considering (1, 2, ..., 10)
        long long count = a[i]; // The count of how many times `num` appears

        // Create a new set to store updated products
        std::set<long long> new_dp;

        // Try multiplying current products with all powers of num
        for (long long existing_product : dp) {
            for (long long j = 0; j <= count; j++) {
                long long new_product = existing_product * static_cast<long long>(pow(num, j)) % MOD;
                new_dp.insert(new_product);
            }
        }

        // Update dp to include the new products
        dp = new_dp;
    }

    // The number of different products is the size of the dp set
    std::cout << dp.size() << std::endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3976kb

input:

0 1 0 1 0 0 0 1 0 0

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: -100
Time Limit Exceeded

input:

0 1000000000 100000000 0 0 0 0 0 0 0

output:


result: