結果
問題 | No.802 だいたい等差数列 |
ユーザー |
![]() |
提出日時 | 2023-07-21 13:10:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,341 bytes |
コンパイル時間 | 4,123 ms |
コンパイル使用メモリ | 253,756 KB |
最終ジャッジ日時 | 2025-02-15 16:07:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | AC * 3 WA * 7 TLE * 1 -- * 19 |
ソースコード
#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);}#endifconst ll MOD=1000000007;void fmod(vl &f){for(auto &e:f){if(e >= MOD) e %= MOD;}}ll logic(){vl f(M+1,1); f.at(0)=0;vl g(D2+1,1);rep(i,D1)g.at(i)=0;int n=N-1;while(n){if(n & 1){f = convolution_ll(f,g);ll fsz = f.size();if(fsz > M+1) f.resize(M+1);fmod(f);#ifdef DEBUGshow("n fsz sz",n,fsz,f.size());rep(i,f.size())if(f.at(i)>0)cout<<i<<","<<f.at(i)<<" ";cout<<endl;#endif}g = convolution_ll(g,g);ll gsz = g.size();if(gsz > M+1) g.resize(M+1);fmod(g);#ifdef DEBUGshow("n gsz sz",n,gsz,g.size());rep(i,g.size())if(g.at(i)>0)cout<<i<<","<<g.at(i)<<" ";cout<<endl;#endifn >>= 1;}#ifdef DEBUGshow("g",g);show("f",f);#endifmint ans=0;rep(i,min((ll)f.size(),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);