結果

問題 No.1269 I hate Fibonacci Number
コンテスト
ユーザー publfl
提出日時 2020-10-23 23:59:09
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,924 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 560 ms
コンパイル使用メモリ 59,504 KB
実行使用メモリ 51,456 KB
最終ジャッジ日時 2024-07-21 13:59:24
合計ジャッジ時間 2,957 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 3 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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