結果
問題 | No.802 だいたい等差数列 |
ユーザー |
![]() |
提出日時 | 2024-04-13 14:44:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 5,855 bytes |
コンパイル時間 | 4,884 ms |
コンパイル使用メモリ | 320,744 KB |
実行使用メモリ | 26,336 KB |
最終ジャッジ日時 | 2024-10-03 00:08:19 |
合計ジャッジ時間 | 7,011 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<ll, ll>;using tp = tuple<ll, ll, ll>;template <class T>using vec = vector<T>;template <class T>using vvec = vector<vec<T>>;#define all(hoge) (hoge).begin(), (hoge).end()#define en '\n'#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)#define REP(i, n) rep(i, 0, n)#define REP2(i, n) rep2(i, 0, n)constexpr long long INF = 1LL << 60;constexpr int INF_INT = 1 << 25;constexpr long long MOD = (ll)1e9 + 7;// constexpr long long MOD = 998244353LL;static const ld pi = 3.141592653589793L;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")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;}struct Edge {int to, rev;ll cap;Edge(int _to, int _rev, ll _cap) : to(_to), rev(_rev), cap(_cap) {}};typedef vector<Edge> Edges;typedef vector<Edges> Graph;void add_edge(Graph &G, int from, int to, ll cap, bool revFlag, ll revCap) {G[from].push_back(Edge(to, (int)G[to].size(), cap));if(revFlag)G[to].push_back(Edge(from, (int)G[from].size() - 1, revCap));}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % 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 = (int)(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, t;while(b > 0) {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;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt<mod>(t);return (is);}static int get_mod() { return mod; }};using mint = ModInt<MOD>;template <class T>struct Combination {vector<T> fact_, inv_, finv_;constexpr Combination() {}constexpr Combination(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n + 1);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].get_mod();for(int i = 2; i < n; i++) {fact_[i] = fact_[i - 1] * i;inv_[i] = -inv_[MOD % i] * (MOD / i);finv_[i] = finv_[i - 1] * inv_[i];}}constexpr T nPr(int n, int k) const noexcept {if(n < k || n < 0 || k < 0)return 0;return fact_[n] * finv_[n - k];}constexpr T nCr(int n, int k) const noexcept {if(n < k || n < 0 || k < 0)return 0;if(n < MOD)return fact_[n] * finv_[k] * finv_[n - k];// Lucasの定理T ret = 1;while(n || k) {ll _n = n % MOD, _k = k % MOD;n /= MOD;k /= MOD;ret *= nCr(_n, _k);}return ret;}constexpr T nHr(int n, int k) const noexcept {if(n <= 0 || k < 0)return 0;return nCr(n + k - 1, k);}constexpr T fact(int n) const noexcept {if(n < 0)return 0;return fact_[n]; // n!}constexpr T inv(int n) const noexcept {if(n < 0)return 0;return inv_[n]; // 1/n}constexpr T finv(int n) const noexcept {if(n < 0)return 0;return finv_[n]; // 1/n!}};void solve() {ll n, m, d1, d2;cin >> n >> m >> d1 >> d2;Combination<mint> com(n + m);// f=(x^D1-x^(D2+1))^(N-1)vec<mint> f(m + 1, 0);REP(i, n) {ll k = d1 * (n - 1 - i) + (d2 + 1) * i;if(k > m)continue;if(i % 2)f[k] -= com.nCr(n - 1, i);elsef[k] += com.nCr(n - 1, i);}// g=(1-x)^(-N-1)vec<mint> g(m + 1, 0);REP(i, m + 1) {g[i] = com.nCr(n + i, n);}mint ans = 0;REP(i, m) {ll j = m + 1 - i - 2;ans += f[i] * g[j];}cout << ans << en;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// cout << fixed << setprecision(10);// ll t;// cin >> t;// REP(i, t - 1) {// solve();// }solve();return 0;}