QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#713998 | #7128. Huge products | hejinming983282 | TL | 0ms | 3976kb | C++23 | 1.3kb | 2024-11-05 21:12:36 | 2024-11-05 21:12:36 |
Judging History
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