E. Count The Blocks ～ダブルカウントにより本数を数える～

1800 
例
N = 10
len = 3

はじっこについて、左端の３つに10種類のうちのどれかを置く
たとえば1を置いたとする
111*******

その隣は1以外の何か。たとえば2を置いたとする
1112******

editorialではそれ以外は10種類の自由度があるとしている
（＊には10種類の数字の何でも入る）
なので、例えば下記のものも含まれる
1112**2111

---

同様に右端からも同じように数えるので、同様に
1112**2111
が作れてしまう。これはダブルカウントでは！？
  • 解説つづき
    • 今回の問題は「ダブルカウントすることで本数を数えている」と理解した
    • 「長さ３を含む数字はいくつあるか？」ではなく「長さ３のブロックは何本とれるか？」の問題であることに注意
    • たとえば1112332111なら、2本分カウントするのが正しい
    • なのでダブルカウントすることで正しく数えられる。これは新鮮な体験だった
ll N; 
ll f(ll len){
  if(len==N) return 10;

  mint sum = 0;

  // side
  sum += mod_pow(10,N-len) * 9;
  sum += mod_pow(10,N-len) * 9;

  // inner
  sum += (N-len-1) * 9 * 9 * mod_pow(10,N-len-1);

  return sum.x;
}

int main(){
    // input
    cin>>N;
    
    VI Ans;
    FOR(i,1,N+1){
      ll num = f(i);
      Ans.push_back(num);
    }
    print_vector(Ans);
    
    return 0;
}