結果

問題 No.3089 Base M Numbers, But Only 0~9
ユーザー 沙耶花
提出日時 2025-04-04 21:50:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 835 bytes
コンパイル時間 6,201 ms
コンパイル使用メモリ 252,048 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-04-04 21:51:10
合計ジャッジ時間 6,058 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL

long long get(long long n,long long b){
	return (n + 9 - b) / 10;
}

int main() {
	
	long long m;
	cin>>m;
	string s;
	cin>>s;
	int n = s.size();
	vector<mint> ps(n+1,1),ss(n+1,1);

	rep(i,s.size()){
		mint v = get(m,s[i]-'0');
		if(i==0 && s[i]=='0')v--;
		ps[i+1] = ps[i] * v;
		ss[i] = v;
	}
	for(int i=n;i>=1;i--)ss[i-1] *= ss[i];
	mint ans = 0;
	rep(i,n){
		mint v = ps[i] * ss[i+1];
		v *= mint(m).pow(n-1-i);
		
		{
			mint sum = 0;
			mint nn = get(m,s[i]-'0');
			sum += nn * (s[i]-'0');
			sum += (nn * (nn-1) / 2)*10;
			ans += v * sum;
		}
		
	}
	cout<<ans.val()<<endl;
}
0