結果
| 問題 |
No.1269 I hate Fibonacci Number
|
| コンテスト | |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-10-24 14:38:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,093 ms / 3,000 ms |
| コード長 | 8,142 bytes |
| コンパイル時間 | 1,379 ms |
| コンパイル使用メモリ | 119,208 KB |
| 実行使用メモリ | 93,804 KB |
| 最終ジャッジ日時 | 2024-07-21 15:15:19 |
| 合計ジャッジ時間 | 11,812 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
static class Program{
const int mod=(int)1e9+7;
static void Main(){
Sc sc=new Sc();
var s=sc.La;
var h=new long[93];
h[0]=0;h[1]=1;
var lik=new List<string>();
for(int i = 2;i<h.Length;i++) {
h[i]=h[i-1]+h[i-2];
if(h[i]>=s[1]&&h[i]<=s[2]){
var t=h[i].ToString();
var bo=true;
for(int j = 0;j<lik.Count&&bo;j++) {
var z=Ex.Za1(lik[j]+"#"+t,0);
for(int k = lik[j].Length+1;k<z.Length;k++) {
if(z[k]==lik[j].Length){
bo=false;
break;
}
}
}
if(bo){lik.Add(t);}
}
}
Mint ans=Fp(10,s[0])-1;
if(lik.Count==0){
Console.WriteLine(ans);
return;
}
Ac ac=new Ac(lik.ToArray(),'0','9');
var dp=new Dictionary<int,Mint>[s[0]+2];
for(int i = 0;i<=s[0]+1;i++) {dp[i]=new Dictionary<int,Mint>();}
dp[0].Add(0,1);
for(int i = 0;i<=s[0];i++) {
foreach(var e in dp[i]){
if(ac.h[e.Key].stl.Count!=0){
ans-=e.Value*Fp(10,s[0]-i);
continue;
}
for(int j = 0;j<10;j++) {
var d=ac.Av(ac.h[e.Key],(char)('0'+j));
if(dp[i+1].ContainsKey(d.Item1.n)){dp[i+1][d.Item1.n]+=e.Value;}
else{dp[i+1].Add(d.Item1.n,e.Value);}
}
}
}
Console.WriteLine(ans);
}
static long Fp(long x,long e){
long r=1;
while(e>0){
if((e&1)>0){r*=x;r%=mod;}
x=(x*x)%mod;
e>>=1;
}
return r;
}
}
public class Ac{
static private int o;
public int n,cnt=1;
public Nd root;
public Nd[] h;
public Nd[] q;
public class Nd{
public Nd[] ar;
public List<Nd> li=new List<Nd>();
public Nd sx;
public List<string> stl=new List<string>();
public int c,f=0,n;
public bool b=false;
public Nd(int c,int f){this.c=c-o;this.f=f;}
public override string ToString(){
var t="n:"+n.ToString("d2")+" f:"+f.ToString()+" c:"+(char)(c+o)+" pr:"+(sx==null?0:sx.n).ToString("d2")+" "+li.Count.ToString("d2")+":";
Nd g=this;while(g.ar==null){g=g.sx;}
for(int j=0;j<g.ar.Length;j++){t+=(b&&ar[j]!=null?(char)(j+o):'-');}
t+=" "+string.Join(" ",stl);
return t;
}
}
public Ac(string[] t,int a,int z){
n=z-a+1;
o=a;
root=new Nd(a-1,0);
q=new Nd[t.Length];
for(int i = 0;i<t.Length;i++) {
var r=root;
for(int j = 0;j<t[i].Length;j++) {
if(!r.b){r.ar=new Nd[n];r.b=true;}
if(r.ar[t[i][j]-o]==null){r.li.Add(r=r.ar[t[i][j]-o]=new Nd(t[i][j],j+1));cnt++;}
else{r=r.ar[t[i][j]-o];}
}
q[i]=r;
r.stl.Add(t[i]);
}
h=new Nd[cnt];
h[0]=root;
int p=1;
var qu=new Queue<Nd>();
for(int i = 0;i<root.li.Count;i++,p++) {
root.li[i].sx=root;
if(root.li[i].b){qu.Enqueue(root.li[i]);}
root.li[i].n=p;
h[p]=root.li[i];
}
while(qu.Count>0){
var e=qu.Dequeue();
for(int i = 0;i<e.li.Count;i++,p++) {
var r=e.sx;
while(r!=null&&(!r.b||r.ar[e.li[i].c]==null)){r=r.sx;}
e.li[i].sx=r!=null?r.ar[e.li[i].c]:root;
if(e.li[i].sx.stl.Count>0){e.li[i].stl.AddRange(e.li[i].sx.stl);}
if(e.li[i].b){qu.Enqueue(e.li[i]);}
e.li[i].n=p;
h[p]=e.li[i];
}
}
}
public void Match(string t,bool bo,Action<int,Nd> f){
var e=root;
for(int i = 0;i<t.Length;i++) {
while(e!=root&&(!e.b||e.ar[t[i]-o]==null)){e=e.sx;}
if(e.ar[t[i]-o]!=null){e=e.ar[t[i]-o];}
if(bo||e.stl.Count!=0){f(i,e);}
}
}
public void Match(string t,bool bo,Func<int,Nd,bool> f){
var e=root;
for(int i = 0;i<t.Length;i++) {
while(e!=root&&(!e.b||e.ar[t[i]-o]==null)){e=e.sx;}
if(e.ar[t[i]-o]!=null){e=e.ar[t[i]-o];}
if(bo||e.stl.Count!=0){
if(!f(i,e)){break;}
}
}
}
public (Nd,bool) Av(Nd e,char c){
var bo=true;
if(!e.b||e.ar[c-o]==null){bo=false;}
while(e!=root&&(!e.b||e.ar[c-o]==null)){e=e.sx;}
if(e.ar[c-o]!=null){e=e.ar[c-o];}
return (e,bo);
}
}
public struct Mint{
const int mod=(int)1e9+7;
private long d;
public Mint(long d){this.d=d;}
public static implicit operator Mint(long d){return new Mint(d%mod);}
public static explicit operator long(Mint d){return d.d;}
public override string ToString(){return d.ToString();}
public static Mint operator+(Mint a,long b){a.d=(a.d+b)%mod;return a;}
public static Mint operator+(Mint a,Mint b){a.d=(a.d+b.d)%mod;return a;}
public static Mint operator-(Mint a,long b){a.d=(mod+a.d-b)%mod;return a;}
public static Mint operator-(Mint a,Mint b){a.d=(mod+a.d-b.d)%mod;return a;}
public static Mint operator*(Mint a,long b){a.d=(a.d*b)%mod;return a;}
public static Mint operator*(Mint a,Mint b){a.d=(a.d*b.d)%mod;return a;}
public static Mint operator/(Mint a,long b){a.d=(a.d*Mi(b))%mod;return a;}
public static Mint operator/(Mint a,Mint b){a.d=(a.d*Mi(b.d))%mod;return a;}
public static bool operator==(Mint a,long b){return (long)a==b;}
public static bool operator!=(Mint a,long b){return (long)a!=b;}
public override bool Equals(object obj){return false;}
public override int GetHashCode(){return 0;}
private static long Mi(long a){
a=(a+mod)%mod;
long b=mod,u=1,v=0;
while(b>0){
long t=a/b;
a-=t*b;(a,b)=(b,a);
u-=t*v;(u,v)=(v,u);
}
u%=mod;
if(u<0){u+=mod;}
return u%mod;
}
}
static class Ex{
static public int[] Za1(string s,int n){
var a=new int[s.Length];
for(int i=n+1,j=0;i<s.Length;){
while(i+j<s.Length&&s[n+j]==s[i+j]){j++;}
a[i]=j;
if(j==0){i++;continue;}
int k=1;
while(i+k<s.Length&&k+a[n+k]<j){a[i+k]=a[n+k];k++;}
i+=k;
j-=k;
}
a[n]=s.Length-n;
return a;
}
static public int[] Za2(string s,int n){
var a=new int[s.Length];
for(int i=n-1,j=0;i>=0;){
while(i-j>=0&&s[n-j]==s[i-j]){j++;}
a[i]=j;
if(j==0){i--;continue;}
int k=1;
while(i-k>=0&&k+a[n-k]<j){a[i-k]=a[n-k];k++;}
i-=k;
j-=k;
}
a[n]=n+1;
return a;
}
static public int[] Ma(string s){
var a=new int[s.Length];
for(int i=0,j=0;i<s.Length;){
while(i-j>=0&&i+j<s.Length&&s[i-j]==s[i+j]){j++;}
a[i]=j;
int k=1;
while(i-k>=0&&i+k<s.Length&&k+a[i-k]<j){a[i+k]=a[i-k];k++;}
i+=k;
j-=k;
}
return a;
}
}
public class Sc{
public int I{get{return int.Parse(Console.ReadLine());}}
public long L{get{return long.Parse(Console.ReadLine());}}
public double D{get{return double.Parse(Console.ReadLine());}}
public string S{get{return Console.ReadLine();}}
public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
public string[] Sa{get{return Console.ReadLine().Split();}}
public object[] Oa{get{return Console.ReadLine().Split();}}
public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}
public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}
public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}
public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}
public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),double.Parse);}
public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}