結果
| 問題 |
No.269 見栄っ張りの募金活動
|
| コンテスト | |
| ユーザー |
 WarToks
|
| 提出日時 | 2020-03-07 15:12:58 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,554 ms / 5,000 ms |
| コード長 | 10,069 bytes |
| コンパイル時間 | 594 ms |
| コンパイル使用メモリ | 122,112 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-30 16:51:48 |
| 合計ジャッジ時間 | 6,860 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
ソースコード
#include <cstdio>
#include <cstdint>
#include <string>
#include <tuple>
#include <vector>
namespace MyInputAndOutput{
// 入力関係 (cin)
class user_input{
private:
static constexpr unsigned int sizeOfAscii = 128;
bool isBlankChar[sizeOfAscii];
/* < definition of getchar >
reference
MacOS : https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/getchar.3.html
Windows : https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/getchar-nolock-getwchar-nolock?view=vs-2019
Linux : https://linux.die.net/man/3/unlocked_stdio
Ubuntu : http://manpages.ubuntu.com/manpages/trusty/man3/getchar_unlocked.3posix.html
*/
#if defined(__APPLE__)
#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar_unlocked
#elif defined(_WIN32) || defined(_WIN64)
#define DAGGER_GETCHAR_UNLOCKED_DAGGER _getchar_nolock
#elif defined(__linux)
#if _POSIX_C_SOURCE >= 1 || _XOPEN_SOURCE || _POSIX_SOURCE || _BSD_SOURCE || _SVID_SOURCE
#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar_unlocked
#else
#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar
#endif
#else
#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar
#endif
// 符号あり整数を getchar で読み込んで構成する (もし, 0 ~ 9 以外の文字が含まれると困る)
template <typename Tp>
inline void charToInteger(Tp& val) const {
val = 0; int c; while(true){
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
if(c == EOF) return;
if('-' or (not isBlankChar[c])) break;
}
if(c == '-'){
while(true){
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
if(c < '0' or c > '9') break;
val = 10 * val + c - '0';
} val = -val;
}
else{
if(c < '0' or c > '9') return;
do{
val = 10 * val + c - '0';
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
} while('0' <= c and c <= '9');
}
}
// 符号なし整数を getchar で読み込んで構成する (もし, 符号付きだとバグる)
template <typename Tp>
inline void charToUnsignedInteger(Tp& val) const {
val = 0; int c; while(true){
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
if(c == EOF) return;
if(not isBlankChar[c]) break;
}
if(c < '0' or c > '9') return;
do{
val = 10 * val + c - '0';
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
} while(not (c == EOF or isBlankChar[c]));
}
public:
constexpr user_input(void) : isBlankChar(){
for(unsigned int i = 0; i < sizeOfAscii; ++i) isBlankChar[i] = false;
isBlankChar[int('\n')] = true; isBlankChar[int('\t')] = true;
isBlankChar[int(' ')] = true; isBlankChar[int('\v')] = true;
}
inline const user_input& operator >> (int& int_arg) const {
//scanf("%d", &int_arg);
charToInteger<int>(int_arg); return *this;
}
inline const user_input& operator >> (long long int& llint_arg) const {
//scanf("%lld", &llint_arg); return *this;
charToInteger<long long int>(llint_arg); return *this;
}
inline const user_input& operator >> (unsigned int& uint_arg) const {
//scanf("%u", &uint_arg);
charToUnsignedInteger<unsigned int>(uint_arg); return *this;
}
inline const user_input& operator >> (unsigned long long int& ullint_arg) const {
//scanf("%llu", &ullint_arg);
charToUnsignedInteger<unsigned long long int>(ullint_arg); return *this;
}
inline const user_input& operator >> (unsigned long& ulint_arg) const {
charToUnsignedInteger<unsigned long>(ulint_arg); return *this;
}
inline const user_input& operator >> (char* str_arg) const {
scanf("%s", str_arg);
return *this;
}
inline const user_input& operator >> (char& char_arg) const {
do{
if((char_arg = DAGGER_GETCHAR_UNLOCKED_DAGGER()) == EOF) return *this;
} while(isBlankChar[int(char_arg)]);
return *this;
}
inline const user_input& operator >> (std::string& str_arg) const {
str_arg.erase();
int c; while(true){
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
if(c == EOF) return *this;
if(not isBlankChar[c]) break;
}
constexpr unsigned int buffer_size = 128;
char buffer_input[buffer_size]; unsigned int buffer_length = 0;
do{
buffer_input[buffer_length++] = c;
if(buffer_length == buffer_size){
buffer_length = 0; str_arg.append(buffer_input, buffer_size);
}
c = DAGGER_GETCHAR_UNLOCKED_DAGGER();
} while(c != EOF and (not isBlankChar[c]) );
str_arg.append(buffer_input, buffer_length);
return *this;
}
template <typename S, typename T>
inline const user_input& operator >>(std::pair<S, T>& pair_arg) const{
(*this) >> pair_arg.first >> pair_arg.second; return *this;
}
template <typename T>
inline const user_input& operator >>(std::vector<T>& vec) const {
for(T& ele : vec) (*this) >> ele;
return *this;
}
// getchar の define の解除
#undef DAGGER_GETCHAR_UNLOCKED_DAGGER
}; constexpr user_input cin;
void ends(void) {putchar('\0'); }
void endl(void) {putchar('\n'); fflush(stdout);}
void flush(void) {fflush(stdout);}
// 出力関係 (cout)
class user_output{
public:
constexpr user_output(void){}
inline const user_output& operator << (const int int_arg) const{
printf("%d", int_arg); return *this;
}
inline const user_output& operator << (const unsigned int uint_arg) const{
printf("%u", uint_arg); return *this;
}
inline const user_output& operator << (const long long int llint_arg) const {
printf("%lld", llint_arg); return *this;
}
inline const user_output& operator << (const unsigned long long int ullint_arg) const {
printf("%llu", ullint_arg); return *this;
}
inline const user_output& operator << (const unsigned long ulint_arg) const {
printf("%lu", ulint_arg); return *this;
}
inline const user_output& operator << (const double ld_arg) const {
printf("%.16lf", ld_arg); return *this;
}
inline const user_output& operator << (const long double ld_arg) const {
printf("%.16Lf", ld_arg); return *this;
}
inline const user_output& operator << (const char char_arg) const {
putchar(char_arg); return *this;
}
inline const user_output& operator << (const unsigned char uchar_arg) const {
putchar(uchar_arg); return *this;
}
inline const user_output& operator << (const char* str_arg) const {
fputs(str_arg, stdout); return *this;
}
inline const user_output& operator << (const std::string& str_arg) const {
fputs(str_arg.c_str(), stdout); return *this;
}
inline const user_output& operator << (void(* const func_arg)(void)) const {
func_arg(); return *this;
}
template <typename S, typename T>
inline const user_output& operator <<(const std::pair<S, T>& pair_arg) const{
(*this) << pair_arg.first << ' ' << pair_arg.second; return *this;
}
template <typename Tp_name>
inline const user_output& operator << (const std::vector<Tp_name>& vec) const {
const size_t size_of_vec = vec.size();
if(size_of_vec <= 0) return *this;
(*this) << vec[0];
for(size_t index = 1; index < size_of_vec; ++index) (*this) << ' ' << vec[index];
return *this;
}
}; constexpr user_output cout;
// その他出力関数
void binary_output(int64_t value, size_t length = 64){
char out[length + 1];
for(size_t i = 0; i < length; ++i) out[length - 1 - i] = ((value >> i) & 1) ? '1' : '0';
out[length] = '\0'; puts(out);
}
template <typename InputType>
void print(InputType first, InputType last, const char separate_c = ' ', const char end_c = '\n'){
InputType it = first;
while(true){
MyInputAndOutput::cout << *it;
if(++it == last){MyInputAndOutput::cout << end_c; return;}
MyInputAndOutput::cout << separate_c;
}
}
}; namespace MIO = MyInputAndOutput;
class modint{
private:
static constexpr unsigned int mod = 1e9 + 7;
unsigned int val;
public:
modint(unsigned int val = 0):val(val){}
modint& operator += (const modint& other){
if((val += other.val) >= mod) val -= mod; return *this;
}
unsigned int get(void) const noexcept{
return val;
}
};
int main(void){
unsigned int n, S, k; MIO::cin >> n >> S >> k;
unsigned int T = k * n * (n - 1) / 2;
if(S < T){ MIO::cout << "0\n"; return 0; } S -= T;
std::vector<modint> DP(S + 1); DP[0] = 1;
for(unsigned int i = 1; i <= n and i <= S; ++i){
for(unsigned s = S; s >= i; --s){
for(unsigned int t = i; t <= s; t += i) DP[s] += DP[s - t];
}
}
MIO::cout << DP[S].get() << MIO::endl;
return 0;
}