結果
| 問題 |
No.129 お年玉(2)
|
| コンテスト | |
| ユーザー |
 tanimani364
|
| 提出日時 | 2020-06-29 22:07:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,898 bytes |
| コンパイル時間 | 1,830 ms |
| コンパイル使用メモリ | 193,344 KB |
| 最終ジャッジ日時 | 2025-01-11 13:34:53 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | MLE * 3 |
| other | MLE * 46 |
コンパイルメッセージ
main.cpp: In static member function ‘static int ArbitraryModInt::set_mod(int)’:
main.cpp:177:3: warning: no return statement in function returning non-void [-Wreturn-type]
177 | }
| ^
ソースコード
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
template <class T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
ll gcd(ll n, ll m)
{
ll tmp;
while (m != 0)
{
tmp = n % m;
n = m;
m = tmp;
}
return n;
}
ll lcm(ll n, ll m)
{
return abs(n) / gcd(n, m) * abs(m); //gl=xy
}
using namespace std;
template<int mod>
struct Modint{
int x;
Modint():x(0){}
Modint(int64_t y):x((y%mod+mod)%mod){}
Modint &operator+=(const Modint &p){
if((x+=p.x)>=mod)
x -= mod;
return *this;
}
Modint &operator-=(const Modint &p){
if((x+=mod-p.x)>=mod)
x -= mod;
return *this;
}
Modint &operator*=(const Modint &p){
x = (1LL * x * p.x) % mod;
return *this;
}
Modint &operator/=(const Modint &p){
*this *= p.inverse();
return *this;
}
Modint operator-() const { return Modint(-x); }
Modint operator+(const Modint &p) const{
return Modint(*this) += p;
}
Modint operator-(const Modint &p) const{
return Modint(*this) -= p;
}
Modint operator*(const Modint &p) const{
return Modint(*this) *= p;
}
Modint operator/(const Modint &p) const{
return Modint(*this) /= p;
}
bool operator==(const Modint &p) const { return x == p.x; }
bool operator!=(const Modint &p) const{return x != p.x;}
Modint inverse() const{//非再帰拡張ユークリッド
int a = x, b = mod, u = 1, v = 0;
while(b>0){
int t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return Modint(u);
}
Modint pow(int64_t n) const{//繰り返し二乗法
Modint ret(1), mul(x);
while(n>0){
if(n&1)
ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os,const Modint &p){
return os << p.x;
}
};
using modint = Modint<mod>;
template< typename T >
struct Combination {
vector< T > _fact, _rfact, _inv;
Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
_fact[0] = _rfact[sz] = _inv[0] = 1;
for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
_rfact[sz] /= _fact[sz];
for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
}
inline T fact(int k) const { return _fact[k]; }
inline T rfact(int k) const { return _rfact[k]; }
inline T inv(int k) const { return _inv[k]; }
T P(int n, int r) const {
if(r < 0 || n < r) return 0;
return fact(n) * rfact(n - r);
}
T C(int p, int q) const {
if(q < 0 || p < q) return 0;
return fact(p) * rfact(q) * rfact(p - q);
}
T H(int n, int r) const {
if(n < 0 || r < 0) return (0);
return r == 0 ? 1 : C(n + r - 1, r);
}
};
struct ArbitraryModInt {
int x;
ArbitraryModInt() : x(0) {}
ArbitraryModInt(int64_t y) : x(y >= 0 ? y % mod() : (mod() - (-y) % mod()) % mod()) {}
static int &mod() {
static int mod = 0;
return mod;
}
static int set_mod(int md) {
mod() = md;
}
ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
if((x += p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
if((x += mod() - p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
unsigned long long a = (unsigned long long) x * p.x;
unsigned xh = (unsigned) (a >> 32), xl = (unsigned) a, d, m;
asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod()));
x = m;
return *this;
}
ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
*this *= p.inverse();
return *this;
}
ArbitraryModInt operator-() const { return ArbitraryModInt(-x); }
ArbitraryModInt operator+(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) += p; }
ArbitraryModInt operator-(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) -= p; }
ArbitraryModInt operator*(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) *= p; }
ArbitraryModInt operator/(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) /= p; }
bool operator==(const ArbitraryModInt &p) const { return x == p.x; }
bool operator!=(const ArbitraryModInt &p) const { return x != p.x; }
ArbitraryModInt inverse() const {
int a = x, b = mod(), u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ArbitraryModInt(u);
}
ArbitraryModInt pow(int64_t n) const {
ArbitraryModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ArbitraryModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ArbitraryModInt &a) {
int64_t t;
is >> t;
a = ArbitraryModInt(t);
return (is);
}
};
ll dp[10005][10005];
const ll x=1000000000;
void comb(){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=10000;++i){
dp[i][0]=1;
for(int j=1;j<=1000;++j){
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%x;
}
}
}
void solve()
{
ll n,m;
cin>>n>>m;
ll a=m*1000;
n%=a;
n/=1000;
comb();
cout<<dp[m][n]<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(15);
solve();
return 0;
}