cafelier@SRM

TCO10 R3 1000

あとで | 14:23 |

• 方針はあってた
• UTPCのときに、C(n,k)の計算はfactorialの値をメモしておけば定数回のmod演算で済む、とlaycurseさんがおっしゃっていたのを今更ながらに思い出した。
  • そうだそうだ。
  • なので、変にインクリメンタルに計算するのはΣC(n',u)の部分だけでいい

static const int MODVAL = 1000000009;
struct mint
{
   int val;
   mint():val(0){}
   mint(int x):val(x%MODVAL) {}
   mint(LL  x):val(x%MODVAL) {}
};

mint operator+(mint x, mint y) { return x.val+y.val; }
mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
mint POW(mint x, int e) {
   mint v = 1;
   for(;e;x=x*x,e>>=1)
      if(e&1)
         v=v*x;
   return v;
}
mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }

vector<mint> FAC_(1,1);
void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); }
mint FAC(mint x)       { return FAC_[x.val]; }
mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }

class Passwords { public:
   int countValid(int N, int L, int U, int D) 
   {
      FAC_INIT(200000);

      //  Sigma_{D<=d<=N-U-L} [C(N,d) 10^d Sigma_{L<=l,U<=u,u+l=N-d}[ C(N-d,u) 26^u 26^l ] ]
      //= Sigma_{D<=d<=N-U-L} [C(N,d) 10^d 26^(N-d) Sigma_{U<=u<=N-d-L}[ C(N-d,u) ] ]
      //   let f(N') = Sigma_{U<=u<=N'-L}[ C(N',u) ]
      //      then by Pascal's triangle, f(N') = 2*f(N'-1)+C(N'-1,U-1)+C(N'-1,N'-L)

      mint answer=0, f=C(U+L,U);
      for(int d=N-U-L; d>=D; --d)
      {
         answer = answer + C(N,d)*POW(10,d)*POW(26,N-d)*f;
         f = f*2 + C(N-d,U-1) + C(N-d, N-d-L+1);
      }
      return answer.val;
   }
};

• ついでに、今までADDとかMULとか名前付き関数で書いていたmod演算を全部演算子オーバーロードしてみた
• こっちの方がうっかりミスしやすいこともあるのでどっちがいいか微妙だけども
• まあ見やすくてよい