問題

C – Ubiquity

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2021/1/27 解法わからず。

解法

• 条件がない場合は、\(10^N\) パターンある…\((1)\)
• \(0\) が無い場合は、\(9^N\) パターンある…\((2)\)
• \(0\) が \(1\) 個以上ある場合は、\((1)-(2)\) パターンある…\((3)\)
• \(9\) が無い場合は、\(9^N\) パターンある…\((4)\)
• \(9\) が \(1\) 個以上ある場合は、\((1)-(4)\) パターンある…\((5)\)
• \(0\) と \(9\) が無い場合は、\(8^N\) パターンある…\((6)\)
• \(0\) または \(9\) が \(1\) 個以上ある場合は、\((1)-(6)\) パターンある…\((7)\)
• \(0\) と \(9\) が \(1\) 個以上ある場合は、\((3)+(5)-(7)\) パターンある
• 整理して、 \(10^N – 9^N – 9^N + 8^N\) が答えになる。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int main() {
  int N;
  cin >> N;

  mint ans = mint(10).pow(N) - mint(9).pow(N) - mint(9).pow(N) + mint(8).pow(N);
  cout << ans.val() << endl;
  return 0;
}