結果

問題 No.1186 長方形の敷き詰め
ユーザー hedwig100hedwig100
提出日時 2020-08-22 17:08:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 3,113 bytes
コンパイル時間 1,574 ms
コンパイル使用メモリ 170,580 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2024-10-15 11:09:51
合計ジャッジ時間 2,582 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 19 ms
18,748 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 8 ms
8,128 KB
testcase_18 AC 13 ms
13,312 KB
testcase_19 AC 15 ms
15,232 KB
testcase_20 AC 17 ms
16,640 KB
testcase_21 AC 12 ms
12,672 KB
testcase_22 AC 23 ms
18,816 KB
testcase_23 AC 11 ms
11,904 KB
testcase_24 AC 16 ms
16,820 KB
testcase_25 AC 12 ms
11,776 KB
testcase_26 AC 12 ms
12,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;
template<int Modulus>
struct ModInt {
long long x;
ModInt(long long x = 0) :x((x%Modulus + Modulus)%Modulus) {}
constexpr ModInt &operator+=(const ModInt a) {if ((x += a.x) >= Modulus) x -= Modulus; return *this;}
constexpr ModInt &operator-=(const ModInt a) {if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this;}
constexpr ModInt &operator*=(const ModInt a) {(x *= a.x) %= Modulus; return *this;}
constexpr ModInt &operator/=(const ModInt a) {return *this *= a.inverse();}
constexpr ModInt operator+(const ModInt a) const {return ModInt(*this) += a.x;}
constexpr ModInt operator-(const ModInt a) const {return ModInt(*this) -= a.x;}
constexpr ModInt operator*(const ModInt a) const {return ModInt(*this) *= a.x;}
constexpr ModInt operator/(const ModInt a) const {return ModInt(*this) /= a.x;}
friend constexpr ostream& operator<<(ostream& os,const ModInt<Modulus>& a) {return os << a.x;}
friend constexpr istream& operator>>(istream& is,ModInt<Modulus>& a) {return is >> a.x;}
ModInt inverse() const {// x ^ (-1)
long long a = x,b = Modulus,p = 1,q = 0;
while (b) {long long d = a/b; a -= d*b; swap(a,b); p -= d*q; swap(p,q);}
return ModInt(p);
}
ModInt pow(long long N) {// x ^ N
ModInt a = 1;
while (N) {
if (N&1) a *= *this;
*this *= *this;
N >>= 1;
}
return a;
}
};
using mint = ModInt<998244353>;
struct Combination {
int N;
//using mint = ModInt<1000000007>;
//using mint = ModInt<998244353>;
vector<mint> fact,ifact,invs;
Combination(int N): N(N) {
fact.resize(N + 1); ifact.resize(N + 1);
fact[0] = fact[1] = 1;
ifact[0] = ifact[1] = 1;
for (int i = 2;i < N + 1;++i) {fact[i] = fact[i - 1] * i;}
ifact[N] = fact[N].inverse();
for (int i = N;i >= 1;--i) {ifact[i - 1] = ifact[i] * i;}
}
void invs_build() {
invs.resize(N + 1);
invs[1] = 1;
for (int i = 2;i < N + 1;++i) invs[i] = fact[i] * ifact[i - 1];
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n - k];
}
mint npk(int n,int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[n - k];
}
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
ll N,M; cin >> N >> M;
if (N == 1) {
cout << 1 << '\n';
return 0;
}
ll x = M/N;
Combination comb(M);
mint ans = 0;
rep(i,x + 1) {
ll j = M - (ll)N*i;
ans += comb(i + j,i);
}
cout << ans << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0