結果

問題 No.1269 I hate Fibonacci Number
ユーザー publflpublfl
提出日時 2020-10-23 23:59:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,924 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 58,756 KB
実行使用メモリ 51,152 KB
最終ジャッジ日時 2023-09-28 19:18:58
合計ジャッジ時間 3,327 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 1 ms
4,380 KB
testcase_38 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#define MOD 1000000007

int next[5010][10];
int prev[5010],fail[5010];
int possible[5010];
int C = 2;

void make(long long int k)
{
	int start = 1;
	std::vector<int> V;
	while(k)
	{
		V.push_back(k%10);
		k/=10;
	}
	std::reverse(V.begin(),V.end());
	
	int control = 0;
	for(int i=0;i<V.size();i++)
	{
		if(next[start][V[i]]==0)
		{
			next[start][V[i]] = C;
			prev[C] = start;
			possible[C] = control;
			C++;
		}
		start = next[start][V[i]];
		if(possible[start]==1) control = 1;
	}
	possible[start] = 1;
}

void makeFailure()
{
	std::queue<int> Q;
	Q.push(1);
	while(!Q.empty())
	{
		int k = Q.front();
		Q.pop();
		if(k>1)
		{
			if(prev[k]==1) fail[k] = 1;
			else
			{
				int c;
				for(int i=0;i<=9;i++)
				{
					if(next[prev[k]][i]==k)
					{
						c = i;
						break;
					}
				}
				int p = fail[prev[k]];
				while(p>=1)
				{
					if(next[p][c]!=0)
					{
						fail[k] = next[p][c];
						goto u;
					}
					else p = fail[p];
				}
				fail[k] = 0;
				u:;
			}
		}
		for(int i=0;i<=9;i++) if(next[k][i]!=0) Q.push(next[k][i]);
	}
}

int a;
long long int check[5010][5010];
long long int func(int k, int state)
{
	//printf("%d %d : %d!!\n",k,state,possible[state]);
	if(possible[state]==1) return 0;
	else if(k>a) return 1;
	else if(check[k][state]>0) return check[k][state];
	else
	{
		long long int ans = 1;
		for(int i=0;i<=9;i++)
		{
			int p = state;
			while(p>=1)
			{
				if(next[p][i]!=0)
				{
					ans += func(k+1,next[p][i]);
					goto u;
				}
				else p = fail[p];
			}
			ans += func(k+1,1);
			u:;
		}
		return check[k][state] = ans%MOD;
	}
}
int main()
{
	scanf("%d",&a);
	long long int b,c;
	scanf("%lld%lld",&b,&c);
	long long int F1 = 1, F2 = 1;
	if(1>=b) make(F2);
	while(F2<c)
	{
		long long int F3 = F1+F2;
		F1 = F2;
		F2 = F3;
		if(b<=F2&&F2<=c) make(F2);
	}
	makeFailure();
	printf("%lld",func(1,1)-2);
}
0