結果
問題 | No.802 だいたい等差数列 |
ユーザー |
![]() |
提出日時 | 2023-07-20 09:49:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,933 bytes |
コンパイル時間 | 5,011 ms |
コンパイル使用メモリ | 259,516 KB |
最終ジャッジ日時 | 2025-02-15 15:52:26 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 4 |
other | RE * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;//using mint = static_modint<998244353>;using mint = static_modint<1000000007>;ostream &operator<<(ostream &o,const mint &m){cout<<m.val();return o;}using ll = long long;using pl = pair<ll,ll>;using vl = vector<ll>;template<class T> using ve = vector<T>;template<class T> using vv = vector<ve<T>>;template<class T> using vvv = vector<vv<T>>;#define rep(i,n) for(ll i=0;i<(ll)(n);++i)#define reps(i,s,n) for(ll i=(s);i<(ll)(n);++i)#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)#define fi first#define se second#define pb push_back#define eb emplace_back#define be(v) (v).begin(),(v).end()const long long INF = 1e18;#ifdef DEBUG#include <debug.hpp>random_device rd;mt19937 gen(rd());ll random(ll l,ll h){uniform_int_distribution<ll> dist(l,h);return dist(gen);}#endifll N,M,D1,D2;void input(){cin>>N>>M>>D1>>D2;}#ifdef DEBUGvoid showall(){show(N,M,D1,D2);}#endifll logic(){ve<mint> f(M+1,1); f.at(0)=0;vector<mint> g(D2+1,1);rep(i,D1)g.at(i)=0;int n=N-1;while(n){if(n & 1){f = convolution(f,g);}g = convolution(g,g);if(g.size()>M){g.resize(M);}#ifdef DEBUGshow("n g.sz g",n,g.size(),g);#endifn >>= 1;}#ifdef DEBUGshow("f2",f);#endifmint ans=0;rep(i,M+1){ans += f.at(i);}return ans.val();}#ifdef DEBUGll naive(){return 1;}#endifint main(){input();#ifdef DEBUGshowall();cout << "--- Logic ---" << endl;#endifll ans=logic();cout<<ans<<endl;//if(logic())cout<<"Yes"<<endl;//else cout<<"No"<<endl;//while(input())logic();#ifdef DEBUG//show("naive=",naive());#endif#ifdef DEBUG/*rep(q,100){N=random(1LL,1000LL);showall();ll lans=logic(),nans=naive();if(lans!=nans){ show(" WA",lans,nans); break; }else{ show(" AC",lans,nans); }}*/#endifreturn 0;}//cout << fixed << setprecision(9);