ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2965 - F グリッドの番号

問題
提出コード

解法

小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。
dp[i][j][s] = i番目までの数字を入れ終えて、上段に配置した個数がj個かつ、直近k手の上下の配置情報がsのときの配置の通り数
とします。
配るDPを考えると、
dp[i][j][s]を配る箇所は、i+1を上段の左からj+1番目に配置した場合と、下段のi-j + 1番目に配置した場合の2か所です。
それぞれのパターンについて、配置したときに矛盾がないかを確認し、問題が無ければ値を配れば良いです。
矛盾がないかを確認するには、sをもとに状態を復元します。
上段に配置する場合は、上段のj番目の数をチェックしてi+1との差がk以下か、
下段に配置する場合は、上段のi-j+1番目の数と下段のi-j番目の数をチェックして、i+1との差がk以下かチェックすればよいです。

Good Bye 2015 D. New Year and Ancient Prophecy

問題
提出コード
dp[l][r] = [l,r)の文字列を一つの年として見た時の、[l,n)の組み合わせの個数
とします。
[l,r)の文字列を使用した、と言うことは、次に選ぶ[r,x)[l,r)より真に大きい値になる必要があります。
条件は以下の二つで、どちらか片方を満たせばよいです。

  1. r-l \lt x-r
    これは、桁がそもそも大きいパターンです。

  2. r-l = x-rかつ、2つの文字列を左から順に見ていった場合に初めて異なる値を[l,r)についてはa[r,x)についてはbとしたときに、a \lt b
    桁が同じ場合です。

1つめのパターンはすぐに計算できます。2つめのパターンが含まれるか含まれないか、を調べればよいです。
これは、[l,n)についてZ algorithmを適用し、rからの接頭辞がどれだけ一致しているかを見ればよいです。
結局遷移は以下のようになります。

  • r-l = x-rとなるxが含まれる場合
    \displaystyle dp[l][r] = \sum_{i = x}^{n}dp[r][i]

  • 含まれない場合
    \displaystyle dp[l][r] = \sum_{i = x + 1}^{n}dp[r][i]

で計算できます。
累積和を更新しながらDPをすることで、O(N^{2})で解けます。

2019-2020 ACM-ICPC Latin American Regional Programming Contest F. Fabricating Sculptures

リンク 問題文

解法

1段ずつ下からブロックを積んでいくことを考えます。
ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。
dp[i][j] = 区間の幅が残りiで、ブロックの残り個数がj個の際の、そこからの構築通り数
とします。
\displaystyle dp[i][j] = \sum_{k = 1}^{i} ((i - k + 1) \times dp[k][j-k])
となります。
少し分解して、
\displaystyle dp[i][j] =(i + 1) \times \sum_{k = 1}^{i}  dp[k][j-k] - \sum_{k = 1}^{i} ( k  \times dp[k][j-k])
とすると、
\displaystyle sum1[i][j] = \sum_{k = 1}^{i}  dp[k][j-k]
\displaystyle sum2[i][j] = \sum_{k = 1}^{i}  (k \times dp[k][j-k])
とすることで、累積和をループの中で取りながらDPをすることができます。
\displaystyle dp[i][j] =(i + 1) \times sum1[i][j] - sum2[i][j]
という式で計算します。

#include <bits/stdc++.h>
#define MOD (long long)(1e9 + 7)
using namespace std;
 
template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y)
      : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const {
    return ModInt(*this) += p;
  }
  ModInt operator-(const ModInt &p) const {
    return ModInt(*this) -= p;
  }
  ModInt operator*(const ModInt &p) const {
    return ModInt(*this) *= p;
  }
  ModInt operator/(const ModInt &p) const {
    return ModInt(*this) /= p;
  }
  bool operator==(const ModInt &p) const {
    return x == p.x;
  }
  bool operator!=(const ModInt &p) const {
    return x != p.x;
  }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ans(1), mul(x);
    while(n) {
      if(n & 1) ans *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ans;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
 
long long s, b;
vector<vector<ModInt<MOD>>> dp, sum1, sum2;
 
ModInt<MOD> solve();
 
int main() {
  cin >> s >> b;
  b -= s;
  cout << solve() << endl;
  return 0;
}
 
ModInt<MOD> solve() {
  dp.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0));
  sum1.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0));
  sum2.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0));
  dp[0][0] = sum1[0][0] = 1;
  for(int i = 1; i <= s; ++i) {
    for(int j = 0; j <= b; ++j) {
      sum1[i][j] += sum1[i - 1][j];
      sum2[i][j] += sum2[i - 1][j];
      if(j != 0) {
        dp[i][j] = sum1[i][j] * (i + 1);
        dp[i][j] -= sum2[i][j];
      }
      else
        dp[i][j] = 1;
      if(i + j <= b) {
        sum1[i][i + j] += dp[i][j];
        sum2[i][i + j] += dp[i][j] * i;
      }
    }
  }
  return dp[s][b];
}

2019-2020 ACM-ICPC Latin American Regional Programming Contest G. Gluing Pictures

リンク 問題文

解法

これの類題です。
dp[i] = i文字目までの文字列を完成させるのに最小となる連続部分列の個数
とします。すると、この配列は広義単調増加になっているはずなので、
dp[i]は、i文字目を右端とするようなSの部分文字列の中で最長の長さをlとしたとき、dp[i] = dp[i-l] + 1となります。
このlは前計算で求めておくことで、答えを求めることができます。
この前計算にはSuffix ArrayとLCPを用います。"<探したい文字列>#S"と連結した後にLCP配列を作成すると、探したい文字列についてのSAのインデックスの前と後ろそれぞれで、最も近い部分に存在するSの一部から始まる箇所を探します。そして、その間にあるLCPの値の最小値が、求めたいlになります。
前からと後ろからそれぞれループをし、Sの部分文字列があたったらLCPの値をその値に更新、それ以外の場合は現在の値とLCPの値のminを取る、という操作を繰り返しながらメモをします。 探したい文字列それぞれについてSAを構築するとTLEするので、探したい文字列自体も、"#"であらかじめ連結します。

#include <bits/stdc++.h>
#define inf (long long)(1e18)
using namespace std;
 
struct Suffix_Array {
  string str;
  int strlen, nowlen;
  vector<long long> rank, tmp, sa, lcp;
  Suffix_Array(string news = "") {
    str = news;
    strlen = str.size();
    nowlen = 0;
    rank.resize(strlen + 1);
    tmp.resize(strlen + 1);
    sa.resize(strlen + 1);
    construct_sa();
    construct_lcp();
  }
  void construct_sa() {
    auto cmp = [&](int l, int r) {
      if(rank[l] != rank[r]) return rank[l] < rank[r];
      int rx = l + nowlen <= strlen ? rank[l + nowlen] : -1;
      int ly = r + nowlen <= strlen ? rank[r + nowlen] : -1;
      return rx < ly;
    };
 
    for(int i = 0; i <= strlen; ++i) {
      sa[i] = i;
      rank[i] = i < strlen ? str[i] : -1;
    }
    for(nowlen = 1; nowlen <= strlen; nowlen *= 2) {
      sort(sa.begin(), sa.end(), cmp);
      tmp[sa[0]] = 0;
      for(int i = 1; i <= strlen; ++i)
        tmp[sa[i]] = tmp[sa[i - 1]] +
                     (cmp(sa[i - 1], sa[i]) ? 1 : 0);
      for(int i = 0; i <= strlen; ++i) rank[i] = tmp[i];
    }
  }
  void construct_lcp() {
    lcp.resize(strlen + 1);
    for(int i = 0; i <= strlen; ++i) rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for(int i = 0; i < strlen; ++i) {
      int j = sa[rank[i] - 1];
      if(h > 0) --h;
      for(; j + h < strlen && i + h < strlen; ++h)
        if(str[j + h] != str[i + h]) break;
      lcp[rank[i] - 1] = h;
    }
  }
};
 
long long n, sid = -1;
string s;
vector<string> v;
vector<long long> res, vid, memo;
Suffix_Array sa;
 
void solve();
long long calc(int id);
 
int main() {
  cin >> s >> n;
  v.resize(n);
  for(int i = 0; i < n; ++i) cin >> v[i];
  res.resize(n);
  solve();
  for(int i = 0; i < n; ++i) cout << res[i] << endl;
  return 0;
}
 
void solve() {
  string t;
  vid.resize(n);
  for(int i = 0; i < n; ++i) {
    vid[i] = t.size();
    t += v[i] + '#';
  }
  sid = t.size();
  t += s;
  sa = Suffix_Array(t);
  long long now = 0, tsize = t.size();
  memo.assign(tsize + 1, 0);
  for(int i = 0; i < tsize; ++i) {
    if(sa.sa[i] >= sid)
      now = sa.lcp[i];
    else
      now = min(now, sa.lcp[i]);
    memo[i + 1] = max(memo[i + 1], now);
  }
  now = 0;
  for(int i = tsize - 1; i >= 0; --i) {
    if(sa.sa[i + 1] >= sid)
      now = sa.lcp[i];
    else
      now = min(now, sa.lcp[i]);
    memo[i] = max(memo[i], now);
  }
  for(int i = 0; i < n; ++i) res[i] = calc(i);
}
 
long long calc(int id) {
  long long vsize = v[id].size();
  vector<long long> dp(vsize + 1, inf),
      idmemo(vsize + 1, inf);
  dp[0] = 0;
  idmemo[0] = 0;
  for(int i = 0; i < vsize; ++i) {
    long long nowid = vid[id] + i;
    nowid = sa.rank[nowid];
    idmemo[i] = i + memo[nowid] - 1;
    auto it = lower_bound(idmemo.begin(), idmemo.end(), i);
    if(*it < i || dp[it - idmemo.begin()] == inf) continue;
    dp[i + 1] = min(dp[i + 1], dp[it - idmemo.begin()] + 1);
  }
  if(dp[vsize] == inf) return -1;
  return dp[vsize];
}

SWERC 2018 K. Dishonest Driver

問題文

解法

区間DPをします。
dp[i][j] = [i,j)区間に対する最小コスト
とすると、
dp[i][j] = min(dp[i][k] + dp[k][j])
になります。 ただし、[i,k)の文字列を複数回連結すると[i,j)になる場合のみ、
dp[i][j] = min(dp[i][k])
になります。
この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。
ただし、ぴったり複数回連結した場合のみなので、(j-i) % (k-i)が0にならなければなりません。

snuke.hatenablog.com

#include <bits/stdc++.h>
#define inf (long long)1e7
using namespace std;
 
// A[i]: S[0,i-1] longest match(pre and suf)
struct KMP {
  vector<long long> A;
  long long n;
  string s;
  KMP(string _s = "") {
    s = _s;
    n = s.size();
    A.assign(n + 1, 0);
    A[0] = -1;
    for(int i = 0, j = -1; i < n; ++i) {
      while(j >= 0 && s[i] != s[j]) j = A[j];
      ++j;
      // if(i + 1 < n && s[i + 1] == s[j])
      //   A[i + 1] = A[j];
      // else
      A[i + 1] = j;
    }
  }
  inline const long long &operator[](int k) const {
    return (A[k]);
  }
  vector<long long> calccycle() {
    vector<long long> res(n, 0);
    for(int i = 0; i < n; ++i) res[i] = i + 1 - A[i + 1];
    return res;
  }
};
 
long long n;
string s;
vector<vector<long long>> dp;
 
long long solve(long long l, long long r);
 
int main() {
  cin >> n >> s;
  vector<long long> v = KMP(s).calccycle();
  dp.assign(n + 1, vector<long long>(n + 1, inf));
  for(int i = 0; i < n; ++i) dp[i][i + 1] = 1;
  for(int i = 0; i <= n; ++i) dp[i][i] = 0;
  cout << solve(0, n) << endl;
  return 0;
}
 
long long solve(long long l, long long r) {
  if(dp[l][r] != inf) return dp[l][r];
  long long res = r - l,
            cycle = KMP(s.substr(l, r - l))
                        .calccycle()[r - l - 1];
 
  for(int i = l + 1; i < r; ++i) {
    long long now = solve(l, i);
    if((r - l) % cycle != 0 || cycle > i - l ||
       (i - l) % cycle != 0)
      now += solve(i, r);
    res = min(res, now);
  }
  return dp[l][r] = res;
}

2019-2020 ACM-ICPC Latin American Regional Programming Contest バチャ 参加記

Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces

なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします
しろくんsuta君と出ました。

流れ

開始後

僕がAから、suta君がDから、しろくんがMから読むことになりました。順位表からもMがまず解けそうということで、しろくんがそのままACです。
続いて、Eも解けそうということで、suta君がそのままACしました。
suta君がEの実装をしている間に、僕としろくんはGの考察をしていました。
じつは、Gはほぼ似たような問題を解いたことがあり、そこでsuffix arrayとlcpの使い方を一応学んでいたので、頑張って思い出しました。
そのままGをACしました。

僕がGの実装をしている間に、2人がIの考察を行い、Gの実装と平行してIも実装してもらっていたため、直後にIもACしました。

中盤~終盤

次に解けそうなのがK, Lだろう、ということでsuta君がLの読解をしている間に僕としろくんがKを考察しました。
しろくんが「因数分解できたらいいですよね」みたいな感じのことを言い、
(x-a)(x-b)... という式を見せてきたときに僕がいい感じに閃き、解法を思いつきました。
同時にバチャを並走してくださっていたチームメンバーのツイートでもちらほら見かけた、「 2^{63}未満になることが保証されている」を読み間違えて「 2^{63}未満にしなければいけない」にした結果、時間を食いましたが無事AC。
Lは、suta君が問題の読解を終えて聞いたところ、これのちょっとした応用ですね~、つい最近講義でやりました!って言いつつ自分が実装をしました。

バグった!


最後は、皆でFをやっていました。
考察は終わった(一応コンテスト後に通しました)のですが、実装が残り5分しかなくて間に合いませんでした。
途中、DPが3乗(残り個数と、1つ隣の高さを状態に持たせる)から落ちない~って言っていて、3人でEDPCの雑談をしていたのですが、その際に急に解法を思いつきました。


結果

6完です。

雑な解法

F

1行ずつ、下からブロックを積み重ねていきます。次にブロックを置く際は、1つ前の操作でブロックを置いた列にしか置かない、とします。
dp[i][j] = 現在使える幅がi、残りブロック数がjの際の、そこからの置き方
とします。 dp[i][j] = \sum_{k = 1}^{i}(i-k+1)dp[k][j-k]
となります。
このΣの部分を分解します。
sum_{1}[i][c] = \sum_{k = 1}^{i}dp[k][c-k]
sum_{2}[i][c] = \sum_{k = 1}^{i}k \times dp[k][c-k]
として、この累積和も同時並行で求めていくと、上手く計算できます。

G

調べたい文字列をT_{i} (1 \leqq i \leqq N)、元の文字列をSとすると、
T_{1} X T_{2} X T_{3} ... X T_{N} X Sという文字列(ただしXはダミー文字)を作成し、これに対してのsuffix arrayおよびlcp配列を構築します。
すると、調べたい文字列の任意の部分を始点とする、Sとの最長一致部分が、前計算O(\sum |T_{i}| +  |S|)で求まります。
あとは、dp[i] = i文字目までの最小コスト、としていい感じに更新します(自分は配るDPをしました)

K

与えられる文字列を、AHの切り替わりで区切ります。そのときの区切りの個数が、多項式の係数の最大です。
求める多項式P(x) = (x-a)(x-b)...とします。(x-a)aの部分を、AHの区切れ目の値(例えば、i人目がAi+1人目がHならば2i+ 1)に設定すると、うまく問題の条件を満たす多項式になります。P(2i)を計算する際に、(x-a)が、a \lt 2iならば正、a \gt 2iならば負になるので、いい感じになります。

L

そもそもBGの入れ替えが行われない時、最大正方形のDPは、
dp[i][j]= (i,j)を右下とする最大正方形の1辺の長さ
と定義して、dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1となります(そこがBならば0です)。
これを、入れ替えたパターンの行に対しても行い、
dp[t][i][j] = (i,j)を右下とする最大正方形の1辺の長さ( t = 1ならば行のBGを入れ替え)
とすると、上のDPとほぼ同じ遷移で解くことができます。

二項係数の式変形について

ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。

_{(r + 1 +c)}C_{c} =  \sum_{i = 0}^{c} {}_{(r+i)}C _{i}

\displaystyle_{(r + 1 +c)}C_{c}について計算をしたい、とします。
これは、一回の移動で1だけ移動できるとしたときの、座標(0,0)から(r + 1,c)への最短移動経路の経路数です。

\displaystyle \sum_{i = 0}^{c} {}_{(r+i)}C _{i}について計算します。
これは、座標(0,0)から(r,i)への最短経路の場合の数を、0 \leqq i \leqq cについて足し合わせたものです。

f:id:emtubasa:20200211134420p:plain

上の(適当な)図の、水色が今求めたい部分です。その上の行にある、黄色く塗られた部分のマスについて注目します。
水色のマスに行くには、まず黄色のマスの少なくとも1つを通らなければ、たどり着くことはできません。そして、赤い矢印のうちいずれか1つを必ず通ります。しかも、2本以上その矢印を通ることはありません。矢印を通った後は、水色のマスにたどり着くまでひたすら右に進む必要があります。
つまり、赤い矢印それぞれについて経路が重複することはないため、それぞれの赤い矢印について、そこを通る経路数を計算し、その総和を求めれば、それが水色のマスへの経路数になります。
そして、赤い矢印を通る経路数は、赤い矢印の始点である黄色いマスの経路数そのものです((r,i)から(r+1,i)の矢印ならば、(r,i)の経路数である_{(r+i)}C_{i})。よって、結果として矢印の経路数の総和である水色のマスの経路数は、

  •  \displaystyle _{(r + 1 +c)}C_{c} =  \sum_{i = 0}^{c} {}_{(r+i)}C _{i}

となりました。

例題(ABC154 F - Many Many Paths)

F - Many Many Paths

提出コード

\displaystyle \sum_{i = r_{1}}^{r_{2}} \sum_{j = c_{1}}^{c_{2}} {}_{i + j}C_{i}を求める問題です。
式変形をすると、

  • \displaystyle \sum_{i = r_{1}}^{r_{2}} ( \sum_{j = 0}^{c_{2}} \ _{i + j}C_{i}  - \sum_{j = 0}^{c_{1} - 1} {}_{i + j}C_{i} )

となり、ここで\displaystyle _{(r + 1 +c)}C_{c} =  \sum_{i = 0}^{c} {}_{(r+i)}C _{i}を使うと、

  • \displaystyle \sum_{i = r_{1}}^{r_{2}} (_{i + c_{2} + 1}C_{c_{2}}  - {}_{i + c_{1}}C_{c_{1}-1} )

になります。これで計算量が落ち、答えを求めることができます。

\sum_{j = 0}^{n}(j \times {}_{n}C_{j}) = n \times 2^{n-1}

\displaystyle \sum_{j = 0}^{n}(j \times {}_{n}C_{j}) = \sum_{j = 1}^{n}(j \times {}_{n}C_{j}) (j = 0のときj \times {}_{n}C_{j} = 0のため)
\displaystyle  = \sum_{j = 1}^{n}\frac{n!}{(n-j)!(j-1)!} (少し展開してjを削除)
\displaystyle  = \sum_{j = 1}^{n}(n\times \frac{(n-1)!}{(n-j)!(j-1)!}) (nを外にだす)
\displaystyle  = \sum_{j=1}^{n}(n\times {}_{n-1}C_{j-1}) (再びまとめる)
\displaystyle  = n \times \sum_{j=0}^{n-1}{}_{n-1}C_{j} (nをΣの外に出し、jを0-indexedに直す)
\displaystyle  = n \times 2^{n-1} (二項定理) となります。

例題(ABC 150 E - Change a Little Bit)

E - Change a Little Bit

提出コード
できるだけコストの小さいものから使用していくのが良いです。ということで、今回は全パターンの総和を求めるため、Cの順番を変えても差し支えないことから、Cを昇順でソートします。今後、Cは0-indexedだとします。
i番目のビットを変化させるとします。このとき、問題文にも書いてあるように、残っている個数をDとすると、D \times C_{i}のコストがかかります。
iより小さい番号のビットはS,Tともにそろっているとします。これらはiビット存在し、元々のビットパターンが(0,0),(0,1),(1,0),(1,1)の4通りなので、この部分は4^{i} ( = 2^{2i} )通り存在します。
i番目のビットは、(0,1),(1,0)の2通り存在します。
さて、iより後ろの部分は、N-i-1ビット存在します。
この中で、jビットがS,Tで異なっているとします。N-i-1-jビットは初めからそろっていることになります。
そろっているビットは(0,0),(1,1)の2通り、異なるビットも(0,1),(1,0)の2通りです。ということで、ビットの組み合わせ自体は2^{N-i-1}通りです。そして、N-i-1ビットの中から、現在異なっているjビットを選ぶのは、{}_{N-i-1}C_{j}通りとなります。
そして、このときにコストは(j+1) \times C_{i}かかります。
jについては、0 \leqq j \leqq N-i-1の選び方があり、それぞれ総和を求めていかなければなりません。
長々と条件を書きましたが、これらを全てまとめて書くと、

  • \displaystyle \sum_{i=0}^{N-1} (4^{i} \times 2 \times \sum_{j=0}^{N-i-1}(2^{N-i-1} \times {}_{(N-i-1)}C_{j} \times (j+1)\times C_{i}))

2の累乗とC_{i}を外に出してまとめると、

  • \displaystyle \sum_{i=0}^{N-1}(2^{N+i} \times C_{i} \times \sum_{j=0}^{N-i-1}((j+1)\times {}_{(N-i-1)}C_{j}) )

となります。さらに(j+1)の部分を分配法則を用いて変形し、
* \displaystyle \sum_{i=0}^{N-1}(2^{N+i} \times C_{i} \times (\sum_{j=0}^{N-i-1} j \times {}_{(N-i-1)}C_{j} + \sum_{j=0}^{N-i-1} {}_{(N-i-1)}C_{j}) )

とすると、\sum_{j = 0}^{n}(j \times {}_{n}C_{j}) = n \times 2^{n-1}および、二項定理\sum_{j = 0}^{n}{}_{n}C_{j} = 2^{n}から、

  • \displaystyle \sum_{i=0}^{N-1}(2^{N+i} \times C_{i} \times ((N-i-1) \times 2^{(N-i-2)} + 2^{(N-i-1)}) )

となります。これで計算量が落ち、答えを求めることができます。