結果

問題 No.3242 Count 8 Included Numbers (Hard)
コンテスト
ユーザー pengin_2000
提出日時 2025-08-22 21:17:53
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 938 bytes
コンパイル時間 126 ms
コンパイル使用メモリ 26,056 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-22 21:17:54
合計ジャッジ時間 1,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:5:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    5 |         scanf("%s", s);
      |         ^~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
char s[1000006];
int main()
{
	scanf("%s", s);
	long long int i, j, k;
	const long long int p = 998244353;
	long long int dp[2][2][2];
	for (i = 0; i < 2; i++)
		for (j = 0; j < 2; j++)
			dp[0][i][j] = 0;
	dp[0][0][0] = 1;
	for (i = 0; s[i] != '\0'; i++)
	{
		for (j = 0; j < 2; j++)
			for (k = 0; k < 2; k++)
				dp[1][j][k] = 0;
		for (j = 0; j < s[i] - '0'; j++)
		{
			if (j == 8)
				dp[1][1][1] += dp[0][0][0];
			else
				dp[1][1][0] += dp[0][0][0];
			dp[1][1][1] += dp[0][0][1];
		}
		if (s[i] == '8')
			dp[1][0][1] += dp[0][0][0];
		else
			dp[1][0][0] += dp[0][0][0];
		dp[1][0][1] += dp[0][0][1];
		for (j = 0; j < 10; j++)
		{
			if (j == 8)
				dp[1][1][1] += dp[0][1][0];
			else
				dp[1][1][0] += dp[0][1][0];
			dp[1][1][1] += dp[0][1][1];
		}
		for (j = 0; j < 2; j++)
			for (k = 0; k < 2; k++)
				dp[0][j][k] = dp[1][j][k] % p;
	}
	printf("%lld\n", (dp[0][0][1] + dp[0][1][1]) % p);
	return 0;
}
0