結果

問題 No.3240 Count 8 Included Numbers (Easy)
コンテスト
ユーザー ルク
提出日時 2025-08-22 21:16:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 882 bytes
コンパイル時間 2,966 ms
コンパイル使用メモリ 278,280 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-22 21:16:37
合計ジャッジ時間 3,827 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include<cstdio>
# include<bits/stdc++.h>

using namespace std;

//Nは桁数が大きい場合があるので文字列として受け取る
string N;
vector<long long> n;  //Nの各桁の数字を格納するベクター
int dp[900000][2][2];
int mod = 998244353;

int main(){
  cin>>N;
  
  //ベクターnを構成
  for(auto a : N){
    n.push_back(a-'0');
  }
  int l = N.size();  //nの長さ

  dp[0][0][0] = 1;  //初期条件。他は0で初期化されている
  for(int i = 0; i < l; i++){
    for(int smaller = 0; smaller < 2; smaller++){
      for(int j = 0; j < 2; j++){
        for(int x = 0; x <= (smaller ? 9 : n[i]); x++){
          dp[i + 1][smaller || x < n[i]][j || x == 8] += dp[i][smaller][j];    
          dp[i + 1][smaller || x < n[i]][j || x == 8] %= mod;
        }
      }
    }
  }

  cout << (dp[l][0][1] + dp[l][1][1])%mod << endl;
  
  return 0;
}
0