結果
| 問題 | No.1043 直列大学 |
| ユーザー |
 polylogK
|
| 提出日時 | 2020-05-01 22:25:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 50 ms / 2,000 ms |
| コード長 | 4,389 bytes |
| コンパイル時間 | 2,299 ms |
| コンパイル使用メモリ | 197,352 KB |
| 最終ジャッジ日時 | 2025-01-10 05:07:50 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:149:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘modint<1000000007>::u64’ {aka ‘long unsigned int’} [-Wformat=]
149 | printf("%lld\n", ans.value());
| ~~~^ ~~~~~~~~~~~
| | |
| long long int modint<1000000007>::u64 {aka long unsigned int}
| %ld
main.cpp:116:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
116 | int n, m; scanf("%d%d", &n, &m); std::vector<int> a(n), b(m);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:117:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
117 | for(int i = 0; i < n; i++) scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:118:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
118 | for(int i = 0; i < m; i++) scanf("%d", &b[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:119:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
119 | int A, B; scanf("%d%d", &A, &B);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
#ifndef INCLUDED_MODINT_HPP
#define INCLUDED_MODINT_HPP
#include <iostream>
template <std::uint_fast64_t Modulus>
class modint {
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using i64 = std::int_fast64_t;
inline u64 apply(i64 x) { return (x < 0 ? x + Modulus : x); };
public:
u64 a;
static constexpr u64 mod = Modulus;
constexpr modint(const i64& x = 0) noexcept: a(apply(x % (i64)Modulus)) {}
constexpr modint operator+(const modint& rhs) const noexcept { return modint(*this) += rhs; }
constexpr modint operator-(const modint& rhs) const noexcept { return modint(*this) -= rhs; }
constexpr modint operator*(const modint& rhs) const noexcept { return modint(*this) *= rhs; }
constexpr modint operator/(const modint& rhs) const noexcept { return modint(*this) /= rhs; }
constexpr modint operator^(const u64& k) const noexcept { return modint(*this) ^= k; }
constexpr modint operator^(const modint& k) const noexcept { return modint(*this) ^= k.value(); }
constexpr modint operator-() const noexcept { return modint(Modulus - a); }
constexpr modint operator++() noexcept { return (*this) = modint(*this) + 1; }
constexpr modint operator--() noexcept { return (*this) = modint(*this) - 1; }
const bool operator==(const modint& rhs) const noexcept { return a == rhs.a; };
const bool operator!=(const modint& rhs) const noexcept { return a != rhs.a; };
const bool operator<=(const modint& rhs) const noexcept { return a <= rhs.a; };
const bool operator>=(const modint& rhs) const noexcept { return a >= rhs.a; };
const bool operator<(const modint& rhs) const noexcept { return a < rhs.a; };
const bool operator>(const modint& rhs) const noexcept { return a > rhs.a; };
constexpr modint& operator+=(const modint& rhs) noexcept {
a += rhs.a;
if (a >= Modulus) a -= Modulus;
return *this;
}
constexpr modint& operator-=(const modint& rhs) noexcept {
if (a < rhs.a) a += Modulus;
a -= rhs.a;
return *this;
}
constexpr modint& operator*=(const modint& rhs) noexcept {
a = a * rhs.a % Modulus;
return *this;
}
constexpr modint& operator/=(modint rhs) noexcept {
u64 exp = Modulus - 2;
while (exp) {
if (exp % 2) (*this) *= rhs;
rhs *= rhs;
exp /= 2;
}
return *this;
}
constexpr modint& operator^=(u64 k) noexcept {
auto b = modint(1);
while(k) {
if(k & 1) b = b * (*this);
(*this) *= (*this);
k >>= 1;
}
return (*this) = b;
}
constexpr modint& operator=(const modint& rhs) noexcept {
a = rhs.a;
return (*this);
}
constexpr u64& value() noexcept { return a; }
constexpr const u64& value() const noexcept { return a; }
explicit operator bool() const { return a; }
explicit operator u32() const { return a; }
const modint inverse() const {
return modint(1) / *this;
}
const modint pow(i64 k) const {
return modint(*this) ^ k;
}
friend std::ostream& operator<<(std::ostream& os, const modint& p) {
return os << p.a;
}
friend std::istream& operator>>(std::istream& is, modint& p) {
u64 t;
is >> t;
p = modint(t);
return is;
}
};
#endif
using mint = modint<1000000007>;
int main() {
int n, m; scanf("%d%d", &n, &m); std::vector<int> a(n), b(m);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < m; i++) scanf("%d", &b[i]);
int A, B; scanf("%d%d", &A, &B);
std::vector<mint> x(1e5 + 1), y(1e5 + 1); x[0] = y[0] = 1;
for(int l = 0; l < 2; l++) {
for(int i = 0; i < a.size(); i++) {
std::vector<mint> nxt(x);
for(int j = 0; j < x.size(); j++) {
if(j + a[i] >= x.size()) continue;
nxt[j + a[i]] += x[j];
}
x.swap(nxt);
}
a.swap(b);
x.swap(y);
}
std::vector<mint> s(x.size() + 1);
for(int i = 0; i < x.size(); i++) s[i + 1] = s[i] + x[i];
mint ans = 0;
for(i64 i = 1; i < y.size(); i++) {
int L = std::min((i64)x.size() - 1, i * (i64)A);
int R = std::min((i64)x.size() - 1, i * (i64)B) + 1;
if(1e5 < i * A) continue;
ans += (s[R] - s[L]) * y[i];
}
printf("%lld\n", ans.value());
return 0;
}