2013 TCO Algorithm Round 3A - TrickyInequality

すげー

↓の最後の問題について詳しく書きます
beet-aizu.hatenablog.com

求めるものは、
∑x1=1t∑x2=1t…∑xn=1t(s−∑ni=1xim−n)${\displaystyle \sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t(\genfrac{}{}{0ex}{}{s-\sum _{i=1}^n{x}_i}{m-n})}$
∵
一つ箱を追加して「s以下」を「ちょうどs」に言い換える
追加した箱以外には一つ以上ボールを入れないといけないので
s−(∑ni=1xi)−(m−n)$s-(\sum _{i=1}^n{x}_i)-(m-n)$ 個のボールを m−n+1$m-n+1$ 個の箱に入れる重複組み合わせになる。

ここで、 Y=∑ni=1xi$Y=\sum _{i=1}^n{x}_i$ と置くと、
f(Y)=(s−Ym−n)=(s−Y)(s−Y−1)…(s−Y−(m−n)+1)(m−n)!$f(Y)=(\genfrac{}{}{0ex}{}{s-Y}{m-n})=\frac{(s-Y)(s-Y-1)\dots (s-Y-(m-n)+1)}{(m-n)!}$ は Y のm-n次多項式になる。
この多項式は O((m−n)2)$O((m-n{)}^2)$ くらいで陽に計算できる
f(Y)=∑k=0m−nakYk$f(Y)={\displaystyle \sum _{k=0}^{m-n}{a}_k{Y}^k}$ とおく。

最初の式に対して式変形を行うと
∑x1=1t∑x2=1t…∑xn=1t(s−∑ni=1xim−n)=∑k=0m−nak(∑x1=1t∑x2=1t…∑xn=1tYk)=∑k=0m−nak⎛⎝∑x1=1t∑x2=1t…∑xn=1t(∑i=1nxi)k⎞⎠${\displaystyle \sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t(\genfrac{}{}{0ex}{}{s-\sum _{i=1}^n{x}_i}{m-n})={\displaystyle \sum _{k=0}^{m-n}{a}_k(\sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t{Y}^k)={\displaystyle \sum _{k=0}^{m-n}{a}_k(\sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t{\left(\sum _{i=1}^n{x}_i\right)}^k)}}}$
となる。

(∑i=1nxi)k${\displaystyle {\left(\sum _{i=1}^n{x}_i\right)}^k}$ は、多項係数の性質から ∑d1+d2+…+dn=kk!∏i=1nxididi!${\displaystyle \sum _{d_1+d_2+\dots +d_n=k}k!\prod _{i=1}^n\frac{{x_i}^{d_i}}{d_i!}}$ である。

したがって、 ∑x1=1t∑x2=1t…∑xn=1t(∑i=1nxi)k=∑x1=1t∑x2=1t…∑xn=1t∑d1+d2+…+dn=kk!∏i=1nxididi!=∑d1+d2+…+dn=kk!∏i=1n(∑xi=1txididi!)${\displaystyle \sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t{\left(\sum _{i=1}^n{x}_i\right)}^k={\displaystyle \sum _{x_1=1}^t\sum _{x_2=1}^t\dots \sum _{x_n=1}^t\sum _{d_1+d_2+\dots +d_n=k}k!\prod _{i=1}^n\frac{{x_i}^{d_i}}{d_i!}=\sum _{d_1+d_2+\dots +d_n=k}k!\prod _{i=1}^n\left(\sum _{x_i=1}^t\frac{{x_i}^{d_i}}{d_i!}\right)}}$

これは (∑x=1txdd!)${\displaystyle \left(\sum _{x=1}^t\frac{x^d}{d!}\right)}$ を d(0≤d≤m−n)$d(0\le d\le m-n)$ ごとに計算したものを多項式として捉え、それを繰り返し自乗法を用いて n$n$ 乗することで O((m−n)2logn)$O((m-n{)}^2\log n)$ で求められる。

あとはこれを実装すれば終わり　全体の計算量は O((m−n)2logn)$O((m-n{)}^2\log n)$ になる。

ソースコード

modintは省略

class TrickyInequality {
public:
  using ll = long long;
  using M = Mint<int>;
  vector<M> mul(vector<M> as,vector<M> bs){
    int sz=as.size()+bs.size()-1;
    vector<M> cs(sz,0);
    for(int i=0;i<(int)as.size();i++)
      for(int j=0;j<(int)bs.size();j++)
        cs[i+j]+=as[i]*bs[j];
    return cs;
  }

  int countSolutions(long long s, int t, int n, int m) {
    int d=m-n;

    vector<M> vs({1});
    for(int i=0;i<d;i++){
      vector<M> ws;
      ws.emplace_back(s-i);
      ws.emplace_back(-M(1));
      vs=mul(vs,ws);
    }

    vector<M> sm(d+1,0);
    for(int i=1;i<=t;i++){
      M po(1);
      for(int j=0;j<=d;j++){
        sm[j]+=po;
        po*=M(i);
      }
    }

    {
      M res{1};
      for(int j=1;j<=d;j++){
        res*=M(j);
        sm[j]/=res;
      }

      for(int j=0;j<=d;j++) vs[j]/=res;
    }

    vector<M> dp(d+1,M(0));
    dp[0]=M(1);
    {
      int p=n;
      while(p){
        if(p&1) dp=mul(dp,sm);
        sm=mul(sm,sm);
        p>>=1;
        dp.resize(d+1);
        sm.resize(d+1);
      }
    }

    M ans{vs[0]*dp[0]};
    {
      M res{1};
      for(int j=1;j<=d;j++){
        res*=M(j);
        ans+=vs[j]*dp[j]*res;
      }
    }

    return ans.v;
  }
};