結果

問題 No.3242 Count 8 Included Numbers (Hard)
ユーザー ルク
提出日時 2025-08-22 21:16:02
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 621 ms / 2,000 ms
コード長 882 bytes
コンパイル時間 4,978 ms
コンパイル使用メモリ 215,300 KB
実行使用メモリ 26,056 KB
最終ジャッジ日時 2025-08-22 21:16:20
合計ジャッジ時間 12,796 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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