結果

問題 No.2199 lower_bound and upper_bound
ユーザー maksimmaksim
提出日時 2023-02-10 18:23:49
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 5,982 bytes
コンパイル時間 2,338 ms
コンパイル使用メモリ 185,456 KB
実行使用メモリ 57,904 KB
最終ジャッジ日時 2023-09-21 20:24:23
合計ジャッジ時間 11,537 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 224 ms
42,384 KB
testcase_01 AC 222 ms
42,504 KB
testcase_02 AC 224 ms
42,892 KB
testcase_03 AC 222 ms
42,400 KB
testcase_04 AC 222 ms
42,436 KB
testcase_05 AC 222 ms
42,392 KB
testcase_06 AC 222 ms
42,532 KB
testcase_07 AC 223 ms
42,464 KB
testcase_08 AC 223 ms
42,444 KB
testcase_09 AC 223 ms
42,384 KB
testcase_10 AC 222 ms
42,380 KB
testcase_11 AC 223 ms
42,444 KB
testcase_12 AC 379 ms
56,304 KB
testcase_13 AC 382 ms
56,316 KB
testcase_14 AC 380 ms
56,456 KB
testcase_15 AC 380 ms
56,868 KB
testcase_16 AC 257 ms
45,192 KB
testcase_17 AC 381 ms
57,904 KB
testcase_18 AC 297 ms
48,824 KB
testcase_19 AC 380 ms
56,252 KB
testcase_20 AC 299 ms
49,648 KB
testcase_21 AC 379 ms
55,168 KB
testcase_22 AC 231 ms
42,860 KB
testcase_23 AC 377 ms
55,492 KB
testcase_24 AC 231 ms
43,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
template<int M, int K, int G> struct Fft {
  // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...
  int g[1 << (K - 1)];
  Fft() : g() { //if tl constexpr...
    static_assert(K >= 2, "Fft: K >= 2 must hold");
    g[0] = 1;
    g[1 << (K - 2)] = G;
    for (int l = 1 << (K - 2); l >= 2; l >>= 1) {
      g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;
    }
    assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);
    for (int l = 2; l <= 1 << (K - 2); l <<= 1) {
      for (int i = 1; i < l; ++i) {
        g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;
      }
    }
  }
  void fft(vector<int> &x) const {
    const int n = x.size();
    assert(!(n & (n - 1)) && n <= 1 << K);
    for (int h = __builtin_ctz(n); h--; ) {
      const int l = 1 << h;
      for (int i = 0; i < n >> 1 >> h; ++i) {
        for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {
          const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;
          if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;
          if ((x[j] += t) >= M) x[j] -= M;
        }
      }
    }
    for (int i = 0, j = 0; i < n; ++i) {
      if (i < j) std::swap(x[i], x[j]);
      for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}
    }
  }
  vector<int> convolution(const vector<int> &a, const vector<int> &b) const {
    if(a.empty() || b.empty()) return {};
    const int na = a.size(), nb = b.size();
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    vector<int> x(n, 0), y(n, 0);
    std::copy(a.begin(), a.end(), x.begin());
    std::copy(b.begin(), b.end(), y.begin());
    fft(x);
    fft(y);
    for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;
    std::reverse(x.begin() + 1, x.end());
    fft(x);
    x.resize(na + nb - 1);
    return x;
  }
};
Fft<998244353,23,31> muls;
vector<int> form(vector<int> v,int n)
{
    while(v.size()<n) v.push_back(0);
    while(v.size()>n) v.pop_back();
    return v;
}
vector<int> operator *(vector<int> v1,vector<int> v2)
{
    return muls.convolution(v1,v2);
}
vector<int> operator +(vector<int> v1,vector<int> v2)
{
    while(v2.size()<v1.size()) v2.push_back(0); while(v1.size()<v2.size()) v1.push_back(0);
    for(int i=0;i<v1.size();++i) {v1[i]+=v2[i];if(v1[i]>=p) v1[i]-=p; else if(v1[i]<0) v1[i]+=p;}
    return v1;
}
vector<int> operator -(vector<int> v1,vector<int> v2)
{
    int sz=max(v1.size(),v2.size());while(v1.size()<sz) v1.push_back(0); while(v2.size()<sz) v2.push_back(0);
    for(int i=0;i<sz;++i) {v1[i]-=v2[i];if(v1[i]<0) v1[i]+=p; else if(v1[i]>=p) v1[i]-=p;} return v1;
}
vector<int> trmi(vector<int> v)
{
    for(int i=1;i<v.size();i+=2) {if(v[i]>0) v[i]=p-v[i]; else v[i]=(-v[i]);}
    return v;
}
vector<int> deriv(vector<int> v)
{
    if(v.empty()) return{};
    vector<int> ans(v.size()-1);
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> integ(vector<int> v)
{
    vector<int> ans(v.size()+1);ans[0]=0;
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> mul(vector<vector<int> > v)
{
    if(v.size()==1) return v[0];
    vector<vector<int> > v1,v2;for(int i=0;i<v.size()/2;++i) v1.push_back(v[i]); for(int i=v.size()/2;i<v.size();++i) v2.push_back(v[i]);
    return muls.convolution(mul(v1),mul(v2));
}
vector<int> inv1(vector<int> v,int n)
{
    assert(v[0]!=0);
    int sz=1;v=form(v,n);vector<int> a={inv(v[0])};
    while(sz<n)
    {
        vector<int> vsz;for(int i=0;i<min(n,2*sz);++i) vsz.push_back(v[i]);
        vector<int> b=((vector<int>) {1})-muls.convolution(a,vsz);
        for(int i=0;i<sz;++i) assert(b[i]==0);
        b.erase(b.begin(),b.begin()+sz);
        vector<int> c=muls.convolution(b,a);
        for(int i=0;i<sz;++i) a.push_back(c[i]);
        sz*=2;
    }
    return form(a,n);
}
vector<int> inv(vector<int> v,int n)
{
    v=form(v,n);assert(v[0]!=0);if(v.size()==1) {return {inv(v[0])};} vector<int> v1=trmi(v);
    vector<int> a=v1*v;a=form(a,2*n);
    vector<int> b((n+1)/2);for(int i=0;i<b.size();++i) b[i]=a[2*i];
    vector<int> ans1=inv(b,b.size());vector<int> ans2(n);for(int i=0;i<n;++i) {if(i%2==0) ans2[i]=ans1[i/2]; else ans2[i]=0;}
    return form(v1*ans2,n);
}
vector<int> operator/(vector<int> a,vector<int> b)
{
    while(!a.empty() && a.back()==0) a.pop_back(); while(!b.empty() && b.back()==0) b.pop_back();
    int n=a.size();int m=b.size();if(n<m) return {};
    reverse(a.begin(),a.end());reverse(b.begin(),b.end());vector<int> ans=a*inv(b,n-m+1);while(ans.size()>n-m+1) ans.pop_back();
    reverse(ans.begin(),ans.end());while(!ans.empty() && ans.back()==0) ans.pop_back();return ans;
}
vector<int> operator%(vector<int> a,vector <int> b)
{
    vector<int> ans=a-b*(a/b);while(!ans.empty() && ans.back()==0) ans.pop_back(); return ans;
}
const int maxn=4e5+5;
int fact[maxn];int invf[maxn];
int c(int n,int k)
{
    if(n==(-1) && k==(-1)) return 1;
    if(n<0 || k<0 || n<k) return 0;
    int ans=fact[n];ans*=invf[k];ans%=p;ans*=invf[n-k];ans%=p;return ans;
}
int f(int cn,int sum)
{
    sum+=2*cn;
    return c(sum-1,cn-1);
}
int f2(int cn,int l,int r)
{
    return f(cn+1,r-1)-f(cn+1,l-2);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fact[0]=1;for(int i=1;i<maxn;++i) fact[i]=(fact[i-1]*i)%p; for(int i=0;i<maxn;++i) invf[i]=inv(fact[i]);
    int n,l,r;cin>>n>>l>>r;
    int ans=f2(n,l,r);
    vector<int> g(n+1),t(n+1);
    t[0]=1;for(int i=1;i<=n;++i) t[i]=c(2*i-1,i);
    for(int i=0;i<=n;++i) g[i]=c(r+2*i+1,i);
    vector<int> h=g*inv(t,n+1);
    for(int i=0;i<=n;++i)
    {
        ans-=h[i]*f2(n-i,l-r-2,r-r-2);ans%=p;
    }
    cout<<(ans%p+p)%p;
    return 0;
}
0