読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

arc 059

arc059.contest.atcoder.jp
飴が c個,人が1\cdots iのときの答えを g(c;i)とおけば以下の漸化式が成立する。
{\displaystyle
\begin{align*}
g(c;i)&=\sum_{j=0}^{c} (A_i^j+(A_i+1)^j+\cdots+B_i^j) g(c-j;i-1)\\
&=\sum_{j=0}^{c} \sum_{k=A_i}^{B_i} k^j g(c-j;i-1)
\end{align*}
}
\sum_{k=A_i}^{B_i} k^jの部分は最初に計算しておいてO(1)のオーダで計算できて結局時間計算量はO(CN)

template <long long modulo>
class Modulo
{
private:
  long long pow(long long q)
  {
    long long a=1;
    long long y=x;
    for(;q!=0;q>>=1)
    {
      if(q&1LL)a=(a*y)%mod;
      y=(y*y)%mod;
    }
    return a;
  }
  long long inv(){return pow(mod-2);}

public:
  long long mod = modulo;
  unsigned long long x;
  Modulo() : x(0) {}
  Modulo(signed s) {while(s<0)s+=mod;x=s%mod;}
  Modulo(signed long long s) {while(s<0)s+=mod;x=s%mod;}
  operator int(){return (int) x;}
  operator long long(){return (long long) x;}
  void operator++(){(*this)+=1;}
  void operator--(){(*this)-=1;}
  Modulo &operator+=(Modulo q){if((x+=q.x)>=mod)x-=mod; return *this;}
  Modulo &operator-=(Modulo q){if((x+=mod-q.x)>=mod)x-=mod; return *this;}
  Modulo &operator*=(Modulo q){x=(unsigned long long)x*q.x%mod; return *this;}
  Modulo &operator/=(Modulo q){x=(unsigned long long)x*q.inv()%mod; return *this;}
  Modulo operator+(Modulo q){return Modulo(*this)+=q;}
  Modulo operator-(Modulo q){return Modulo(*this)-=q;}
  Modulo operator*(Modulo q){return Modulo(*this)*=q;}
  Modulo operator/(Modulo q){return Modulo(*this)/=q;}
  template<typename T> Modulo &operator+=(const T q){if((x+=q)>=mod)x-=mod; return *this;}
  template<typename T> Modulo &operator-=(const T q){if((x+=mod-q)>=mod)x-=mod; return *this;}
  template<typename T> Modulo &operator*=(const T q){x=(unsigned long long)x*q%mod; return *this;}
  template<typename T> Modulo &operator/=(const T q){x=(unsigned long long)x*(Modulo(q)).inv()%mod; return *this;}
  template<typename T> Modulo operator+(const T q){return Modulo(*this)+=q;}
  template<typename T> Modulo operator-(const T q){return Modulo(*this)-=q;}
  template<typename T> Modulo operator*(const T q){return Modulo(*this)*=q;}
  template<typename T> Modulo operator/(const T q){return Modulo(*this)/=q;}
  template<typename T> Modulo power(const T q){return Modulo(pow((long long)q));}
};

int a[410],b[410];
Modulo<MOD> dp[410][410];
Modulo<MOD> x[410][410];

int main()
{
  int n,c;cin>>n>>c;
  REP(i,n) cin>>a[i];
  REP(i,n) cin>>b[i];
  FOR(i,0,409)
  {
    x[i][0]=1;
    FOR(j,1,c) x[i][j]=x[i][j-1]*i;
  }
  FOR(j,0,c) FOR(i,1,409)
    x[i][j]+=x[i-1][j];
  dp[0][0]=1;
  FOR(i,0,n)FOR(j,0,c)FOR(k,0,c-j)
    dp[j+k][i+1]+=dp[j][i]*(x[b[i]][k]-x[a[i]-1][k]);
  cout << (ll)(dp[c][n]) << endl;
  return 0;
}