Fibonotci / Eat

两个矩阵快速幂优化的好题

Fibonotci

对于这种转移有循环的函数，因为每一次对初始元素的操作是相同的，那么就可以抽象成在这个循环的前端输入了一个元素，然后经过一番操作，得到了新的元素，然后先考虑没有修改的做法，因为每n个的转移是一样的，那么对于n步内的每一个转移构造一个2*2的矩阵，然后把这些矩阵乘起来，然后如果K是n的整数倍，直接用得到的矩阵快速幂就行了，如果不是，那么剩下不足n个的暴力算就行了

对于有修改的情况，我们可以在每修改的两个位置之间的地方进行快速幂，然后手动跳过去就行了。但是如果修改的位置在一个循环的中间位置，那么从这个位置到这个循环末端剩下的部分组成的循环矩阵需要一种数据结构迅速得到，那么就可以用线段树来维护，每一个节点是一个矩阵，然后就可以维护了。

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <iostream>
  6 #include <algorithm>
  7 using namespace std;
  8 typedef long long LL;
  9 void ot(){cout<<"***"<<endl;}
 10 const int maxn=50010;
 11 LL K,mod,n,m;
 12 LL s[maxn];
 13 struct MM{
 14     LL d[4][4];
 15     void clear(){memset(d,0,sizeof(d));}
 16     void beg(){ memset(d,0,sizeof(d)); d[1][1]=d[2][2]=1;}
 17     void O(){
 18         for(int i=1;i<=2;i++){
 19             for(int j=1;j<=2;j++)
 20                 cout<<d[i][j]<<" "; 
 21             cout<<endl;
 22         }
 23         cout<<endl;
 24     }
 25 };
 26 struct MMM{
 27     LL d[4];
 28     void clear(){memset(d,0,sizeof(d));}
 29 };
 30 MM c;
 31 MM operator * (const MM a,const MM b){
 32     c.clear();
 33     for(int k=1;k<=2;k++)
 34         for(int i=1;i<=2;i++)
 35             for(int j=1;j<=2;j++){
 36                 c.d[i][j]=(c.d[i][j]+b.d[i][k]*a.d[k][j]%mod)%mod;
 37             }
 38     return c;
 39 }
 40 MMM cc;
 41 MMM operator * (const MMM a,const MM b){
 42     cc.clear();
 43     for(int i=1;i<=2;i++)
 44         for(int j=1;j<=2;j++)
 45             cc.d[i]=(cc.d[i]+a.d[j]*b.d[i][j])%mod;
 46     return cc;
 47 }
 48 MM sum[maxn*4];
 49 void Build(int now,int l,int r){
 50     if(l==r){
 51         if(l==0){ sum[now].beg(); return;}
 52         sum[now].d[1][1]=s[l%n]; sum[now].d[1][2]=s[(l-1)%n];
 53         sum[now].d[2][1]=1;    sum[now].d[2][2]=0; 
 54         return;
 55     }
 56     int mid=(l+r)>>1;
 57     Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);
 58     sum[now]=sum[now<<1]*sum[now<<1|1];
 59     /*
 60     cout<<"================="<<endl;
 61     cout<<"lr== "<<l<<"  "<<r<<endl;
 62     sum[now].O();
 63     sum[now<<1].O();
 64     sum[now<<1|1].O();
 65     cout<<"================="<<endl;
 66     */
 67 }
 68 MM e;
 69 int timer;
 70 MM query(int left,int right,int now,int l,int r){
 71     if(left>right) return e;
 72     if(left<=l && r<=right){
 73         return sum[now];
 74     }
 75     int mid=(l+r)>>1; MM ret; ret.beg();
 76     if(left<=mid) ret=ret*query(left,right,now<<1,l,mid);
 77     if(right>mid) ret=ret*query(left,right,now<<1|1,mid+1,r);
 78     return ret;
 79 }
 80 struct Boy{
 81     LL id,to;
 82 }g[maxn];
 83 bool cmp1(const Boy &a,const Boy &b){return a.id<b.id;}
 84 void init(){
 85     scanf("%lld%lld%lld",&K,&mod,&n);
 86     for(int i=0;i<n;i++) scanf("%lld",&s[i]);
 87     scanf("%lld",&m);
 88     for(int i=1;i<=m;i++) scanf("%lld%lld",&g[i].id,&g[i].to);
 89     sort(g+1,g+m+1,cmp1);
 90     Build(1,1,n);
 91     e.beg();
 92 }
 93 MM ksm(MM a,LL b){
 94     MM ret; ret.beg();
 95     while(b){
 96         if(b&1) ret=ret*a;
 97         b>>=1; a=a*a;
 98     }
 99     return ret;
100 }
101 MMM f;
102 void work1(){
103     LL t=K/n,rm=K-K/n*n;
104     if(rm==0) t--,rm=n;
105     MM bs=sum[1];
106     bs=ksm(bs,t);
107     f.d[1]=1; f.d[2]=0;
108     f=f*bs;
109     if(rm-1) bs=query(1,rm-1,1,1,n),f=f*bs;
110     cout<<f.d[1]<<endl;
111 }
112 MMM cun;
113 MM Ask(LL l,LL r){
114     LL len=r-l; MM bs,ha; bs.beg();
115     LL t1,t2,len1,len2;
116     if(l%n==0){
117         bs=query(n,n,1,1,n);  l++;
118     }
119     if(r-l<n){
120         // if(timer) ot();
121         if(r%n>=l%n){
122 
123             bs=bs*query(l%n,r%n-1,1,1,n);
124         }
125         else if(r%n==0){
126 
127             bs=bs*query(l%n,n-1,1,1,n);
128         }
129         else{
130 
131             bs=bs*query(l%n,n,1,1,n);
132             if(r%n-1) bs=bs*query(1,r%n-1,1,1,n);
133             if(timer){
134                 cout<<l%n<<"  "<<r%n-1<<endl;
135             }
136         }
137     }
138     else{
139 
140         if(r%n!=0 && r%n-1==0){
141             // if(timer){
142             //     cout<<"llll== "<<l<<" "<<r<<endl;
143             //     cout<<l%n<<" "<<r%n<<endl;
144             // }
145             t1=l%n? l%n:n;
146             len1=n-t1+1;
147             bs=bs*query(t1,n,1,1,n);
148             len-=len1;
149             LL t=len/n;
150             // if(timer) cout<<"len== "<<len<<endl;
151             ha=sum[1];
152             ha=ksm(ha,t);
153             bs=bs*ha;
154         }
155         else{
156             t1=l%n? l%n:n;
157             len1=n-t1+1;
158             bs=bs*query(t1,n,1,1,n);
159             len-=len1;
160             t2=r%n? r%n-1:n-1;
161             len2=t2;
162             len-=len2;
163             LL t=len/n;
164             ha=sum[1];
165             ha=ksm(ha,t);
166             bs=bs*ha;
167             bs=bs*query(1,t2,1,1,n);
168         }
169     }
170     return bs;
171 }
172 void work2(){
173     LL id,to;
174     LL lst=1; MM bs;
175     f.d[0]=0; f.d[1]=1;
176     int od=82,od1=0;
177     g[0].id=-2; g[m+1].id=-4;
178     for(int i=1;i<=m;i++){
179         id=g[i].id,to=g[i].to;
180         if(id==od || id==od1) timer=1;
181         if(id>=K) break;
182         cun=f;
183         // if(timer){ cout<<"dun== "<<cun.d[1]<<"  "<<cun.d[2]<<endl;}
184         bs=Ask(lst,id);
185         f=f*bs; 
186         lst=id;
187         // if(timer){cout<<"id== "<<id<<" "<<f.d[1]<<endl;}
188         if(g[i].id+1==g[i+1].id){
189             LL t=f.d[1];
190             f.d[1]=(f.d[1]*to%mod+f.d[2]*s[(id-1)%n]%mod)%mod;
191             f.d[2]=t; t=f.d[1];
192             lst=id+1;
193             if(lst==K){cout<<f.d[1]<<endl; return;}
194             while(g[i].id+1==g[i+1].id){
195                 t=f.d[1];
196                 f.d[1]=(f.d[1]*g[i+1].to%mod+f.d[2]*g[i].to%mod)%mod;
197                 f.d[2]=t; t=f.d[1];
198                 lst++;
199                 if(lst==K){cout<<f.d[1]<<endl; return;}
200                 i++;
201             }
202             t=f.d[1];
203             f.d[1]=(f.d[1]*s[lst%n]%mod+f.d[2]*g[i].to%mod)%mod;
204             f.d[2]=t;
205             lst++;
206             // cout<<"lst= "<<lst<<" "<<f.d[1]<<" "<<g[i].id<<endl;
207             if(lst==K) if(lst==K){cout<<f.d[1]<<endl; return;}
208         }
209         else{
210             LL t=f.d[1];
211             f.d[1]=(f.d[1]*to%mod+f.d[2]*s[(id-1)%n]%mod)%mod;
212             f.d[2]=t; t=f.d[1];
213             f.d[1]=(f.d[1]*s[(id+1)%n]%mod+f.d[2]*to%mod)%mod;
214             f.d[2]=t;
215             lst=id+2;
216         }
217         if(id==od || id==od1){timer=0;}
218         if(id+1==K){cout<<f.d[2]<<endl; return;}
219         if(id+2==K){cout<<f.d[1]<<endl; return;}
220     }
221     bs=Ask(lst,K);
222     f=f*bs;
223     cout<<f.d[1]<<endl;
224 }
225 int main(){
226     // check();
227     // freopen("fibonotci4.in","r",stdin);
228     // freopen("a.in","r",stdin);
229     init();
230     if(m==0) work1();
231     else work2();
232 }
View Code

Eat

这个题有20分的暴力，那么直接插头就行了，然后可以发现每一行转移完了之后，发现只有9个有效的状态，那么可以构建一个9*9的状态之间的转移矩阵，然后就可以像上一题一样一段一段的跳就行了

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <iostream>
  6 #include <algorithm>
  7 using namespace std;
  8 typedef long long LL;
  9 const int mod=1000000007;
 10 LL n,m,c,d;
 11 int cnt;
 12 struct Point{LL x,y,nam;}spc[50];
 13 bool cmp1(const Point &a,const Point &b){return a.x==b.x? a.y<b.y:a.x<b.x;}
 14 int q[20],tot,id[200],cun[10];
 15 void Jud(){
 16     int mk=0,S=0;
 17     for(int i=1;i<=m;i++)
 18         if(cun[i]==1) mk++; 
 19         else if(cun[i]==2 && mk) mk--;
 20         else if(cun[i]==2 && mk<=0) return;
 21     if(mk!=0) return;
 22     for(int i=1;i<=m;i++) S|=(cun[i]<<(i-1 << 1));
 23     q[++tot]=S;
 24 }
 25 void dfs(int x){
 26     if(x==m+1){ Jud();return;}
 27     for(int i=0;i<=2;i++){
 28         cun[x]=i; dfs(x+1);
 29     }
 30 }
 31 void find_id(){ 
 32     dfs(1); sort(q+1,q+tot+1); 
 33     for(int i=1;i<=tot;i++) id[q[i]]=i; 
 34 }
 35 struct MM{
 36     LL d[11][11];
 37     void clear(){memset(d,0,sizeof(d));}
 38     void beg(){memset(d,0,sizeof(d)); for(int i=1;i<=tot;i++) d[i][i]=1;}
 39     void O(){
 40         for(int i=1;i<=tot;i++){
 41             for(int j=1;j<=tot;j++)
 42                 cout<<d[i][j]<<" "; cout<<endl;
 43         } cout<<endl;
 44     }
 45 }cc,bs;
 46 MM operator * (const MM &a,const MM &b){
 47     cc.clear();
 48     for(int i=1;i<=tot;i++)
 49         for(int j=1;j<=tot;j++)
 50             for(int k=1;k<=tot;k++)
 51                 cc.d[i][j]=(cc.d[i][j] + a.d[i][k]*b.d[k][j]%mod)%mod;
 52     return cc;
 53 }
 54 struct MMM{
 55     LL d[11];
 56     void clear(){memset(d,0,sizeof(d));}
 57     void O(){for(int i=1;i<=tot;i++) cout<<d[i]<<" "; cout<<endl<<endl;}
 58 }ccc;
 59 MMM operator * (const MMM &a,const MM &b){
 60     ccc.clear();
 61     for(int i=1;i<=tot;i++)
 62         for(int j=1;j<=tot;j++)
 63             ccc.d[i]=(ccc.d[i] + a.d[j]*b.d[j][i]%mod)%mod;
 64     return ccc;
 65 }
 66 MM ksm(MM a,LL b){
 67     MM ret; ret.beg();
 68     while(b){
 69         if(b&1) ret=ret*a;
 70         b>>=1; a=a*a;
 71     }
 72     return ret;
 73 }
 74 struct Hash_map{
 75     int key;
 76     struct edge{int u,nxt; LL v;}g[1<<20];
 77     int adj[77543],e;
 78     void clear(){memset(adj,-1,sizeof(adj)); e=0;}
 79     Hash_map(){key=76543; clear();}
 80     LL& newnode(int u){
 81         g[e].u=u; g[e].v=0;
 82         g[e].nxt=adj[u%key]; adj[u%key]=e++;
 83         return g[e-1].v;
 84     }
 85     LL& operator [] (const int u){
 86         for(int i=adj[u%key];i!=-1;i=g[i].nxt){
 87             if(u==g[i].u) return g[i].v;
 88         }
 89         return newnode(u);
 90     }
 91 }f[2];
 92 void Set(int &S,int x,int w){
 93     x=(x-1 << 1);
 94     S|=3<<x;
 95     S^=3<<x;
 96     S|=w<<x;
 97 }
 98 int Get(int S,int x){return (S>>(x-1 << 1))&3;}
 99 int find(int S,int x){
100     int d=(Get(S,x)==1?1:-1),p,mk=0;
101     for(int i=x;i&&i<=m+1;i+=d){
102         p=Get(S,i);
103         if(p==1) mk++;
104         else if(p==2) mk--;
105         if(!mk) return i;
106     }
107 }
108 int w[10],now,ey;
109 LL ans;
110 void see(int S){ for(int i=1;i<=m+1;i++) cout<<Get(S,i)<<" "; cout<<endl;}
111 void check(){
112     for(int i=0;i<f[now].e;i++){
113         cout<<" S= "<<f[now].g[i].u<<" :::"; see(f[now].g[i].u);
114         cout<<"  val= "<<f[now].g[i].v<<endl;
115     }
116 }
117 void DP(int y,int od){
118     now^=1; int lst=now^1,p1,p2,S; LL val; f[now].clear();
119     for(int i=0;i<f[lst].e;i++){
120         S=f[lst].g[i].u; val=f[lst].g[i].v;
121         p1=Get(S,y); p2=Get(S,y+1);
122         if(w[y]==-1){
123             if(!p1 && !p2) f[now][S]=(f[now][S]+val)%mod;
124             continue;
125         }
126         if(!p1 && !p2){
127             if(!w[y]) f[now][S]=(f[now][S]+val)%mod;
128             if(od && y==ey && !S) ans=(ans+val)%mod;
129             if(!od && y!=m) Set(S,y,1), Set(S,y+1,2), f[now][S]=(f[now][S]+val)%mod;
130         }
131         else if(!p1 && p2){
132             if(y!=m) f[now][S]=(f[now][S]+val)%mod;
133             if(!od) Set(S,y,p2),Set(S,y+1,0),f[now][S]=(f[now][S]+val)%mod;
134         }
135         else if(p1 && !p2){
136             if(!od) f[now][S]=(f[now][S]+val)%mod;
137             if(y!=m) Set(S,y+1,p1),Set(S,y,0),f[now][S]=(f[now][S]+val)%mod;
138         }
139         else if(p1==1 && p2==2){
140             Set(S,y,0),Set(S,y+1,0); 
141             if(od && y==ey && !S) ans=(ans+val)%mod;
142             f[now][S]=(f[now][S]+val)%mod;
143         }
144         else if(p1==1 && p2==1){Set(S,find(S,y+1),1),Set(S,y,0),Set(S,y+1,0);f[now][S]=(f[now][S]+val)%mod;}
145         else if(p1==2 && p2==2){Set(S,find(S,y),2),Set(S,y,0),Set(S,y+1,0); f[now][S]=(f[now][S]+val)%mod;}
146         else if(p1==2 && p2==1){Set(S,y,0),Set(S,y+1,0); f[now][S]=(f[now][S]+val)%mod;}
147     }
148 }
149 void make_MM(){
150     int S,u; memset(w,0,sizeof(w)); bs.clear();
151     for(int i=1;i<=tot;i++){
152         now=0; f[now].clear(); f[now][q[i]<<2]=1;
153         for(int j=1;j<=m;j++) DP(j,0);
154         for(int j=0;j<f[now].e;j++){
155             u=f[now].g[j].u;
156             bs.d[i][id[u]]+=f[now].g[j].v;
157         }
158     }
159 }
160 MMM F;
161 void work(){
162     F.d[id[0]]=1; MM fast;
163     LL lst=0,i; LL t;
164     for(i=1;i<=cnt;i++){
165         t=spc[i].x-lst-1; fast=bs;
166         fast=ksm(fast,t); F=F*fast; lst=spc[i].x-1;
167         if(spc[i].x==n) break;
168         memset(w,0,sizeof(w));
169         w[spc[i].y]=spc[i].nam;
170         while(spc[i].x==spc[i+1].x) i++,w[spc[i].y]=spc[i].nam;
171         now=0; f[now].clear();
172         for(int j=1;j<=tot;j++) f[now][q[j]<<2]=F.d[j];
173         for(int j=1;j<=m;j++) DP(j,0);
174         F.clear();
175         for(int j=0;j<f[now].e;j++) F.d[id[f[now].g[j].u]]=f[now].g[j].v;
176         lst=spc[i].x;
177     }
178     t=n-lst-1; fast=bs;
179     fast=ksm(fast,t); F=F*fast;
180     memset(w,0,sizeof(w));
181     while(i<=cnt) w[spc[i].y]=spc[i].nam;
182     for(int j=1;j<=m;j++) if(w[j]>=0) ey=j;
183     now=0; f[now].clear();
184     for(int j=1;j<=tot;j++) f[now][q[j]<<2]=F.d[j];
185     for(int j=1;j<=m;j++) DP(j,1);
186     cout<<ans<<endl;
187 }
188 int main(){
189     // freopen("eat6.in","r",stdin);
190     scanf("%lld%lld%lld%lld",&n,&m,&c,&d);
191     for(int i=1;i<=c;i++) spc[++cnt].nam=-1,scanf("%lld%lld",&spc[cnt].x,&spc[cnt].y);
192     for(int i=1;i<=d;i++) spc[++cnt].nam= 1,scanf("%lld%lld",&spc[cnt].x,&spc[cnt].y);
193     sort(spc+1,spc+cnt+1,cmp1); spc[cnt+1].x=spc[cnt+1].y=-10;
194     find_id();
195     make_MM();
196     work();
197 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/FOXYY/p/8391504.html