做金融在那个网站上找工作/市场营销计划

题目链接：http://codeforces.com/contest/1182/problem/E

题意：给你一个公式，只求x>=4的情况，告诉你c,f1,f2,f3，问你fx为多少，x最大可到1e18。

做法：

        其实想想也简单，就是四个矩阵快速幂，对于后面的三个量,是左下角的图，对于c来说是右下角的图。

      就是敲敲麻烦，但是这里因为指数过大，所以需要做一个欧拉降幂，a^b%mod c=a^(b%ol(c)+ol(c)) %mod c,而1e9+7为质数，所以ol(mod)=1e9+6。

      wa也不知道在哪里...原来是知识储备不够，咳咳。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll olmod=1e9+6;
ll n,f1,f2,f3,nc;
struct matrix{ll aim[6][6];void mem(){memset(aim,0,sizeof(aim));}void clea(){memset(aim,0,sizeof(aim));for(int i=1;i<=4;i++)aim[i][i]=1;}
};
matrix mul(matrix a,matrix b){matrix ans;memset(ans.aim,0,sizeof(ans.aim));for(ll i=1;i<=4;i++){for(ll j=1;j<=4;j++){for(ll k=1;k<=4;k++){ans.aim[i][j]=(ans.aim[i][j]+a.aim[i][k]*b.aim[k][j])%olmod;}}}return ans;
}
matrix mulc(matrix a,matrix b){matrix ans;memset(ans.aim,0,sizeof(ans.aim));for(ll i=1;i<=5;i++){for(ll j=1;j<=5;j++){for(ll k=1;k<=5;k++){ans.aim[i][j]=(ans.aim[i][j]+a.aim[i][k]*b.aim[k][j])%olmod;}}}return ans;
}
matrix quick(matrix a,ll k){matrix ans;ans.clea();while(k){if(k&1){ans=mul(ans,a);}a=mul(a,a);k/=2;}return ans;
}
ll Cal(ll x,matrix st){matrix a;a.mem();a.aim[1][1]=a.aim[1][2]=a.aim[1][3]=1;for(int i=2;i<=4;i++)a.aim[i][i-1]=1;matrix ans=quick(a,x);ans=mul(ans,st);return ans.aim[1][1]%olmod;
}
ll Calc(ll ti,matrix st){
matrix a;a.mem();a.aim[1][1]=a.aim[1][2]=a.aim[1][3]=1;for(int i=2;i<=3;i++)a.aim[i][i-1]=1;a.aim[1][4]=2,a.aim[1][5]=-4;a.aim[4][5]=a.aim[4][4]=a.aim[5][5]=1;matrix ans;ans.clea();while(ti){if(ti&1){ans=mulc(ans,a);}a=mulc(a,a);ti/=2;}ans=mulc(ans,st);return ans.aim[1][1]%olmod;
}
ll qb(ll a,ll b){ll ans=1;//printf("%lld %lld ",a,b);while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b/=2;}//printf("%lld\n",ans);return ans;
}
ll Each(ll a,ll b,ll c,ll d){ll ret=1;ret=qb(nc,a)*qb(f1,b)%mod*qb(f2,c)%mod*qb(f3,d)%mod;return ret;
}
int main(){scanf("%lld%lld%lld%lld%lld",&n,&f1,&f2,&f3,&nc);if(n<=6){if(n==4) printf("%lld\n",Each(2,1,1,1));else if(n==5) printf("%lld\n",Each(6,1,2,2));else printf("%lld\n",Each(12,2,3,4));}else{ll ti=n-6;matrix st;st.mem();st.aim[1][1]=14,st.aim[2][1]=6,st.aim[3][1]=2,st.aim[4][1]=6,st.aim[5][1]=1;ll numc=Calc(ti,st);st.aim[1][1]=2,st.aim[2][1]=1,st.aim[3][1]=1;ll numf1=Cal(ti,st);st.aim[1][1]=3,st.aim[2][1]=2,st.aim[3][1]=1;ll numf2=Cal(ti,st);st.aim[1][1]=4,st.aim[2][1]=2,st.aim[3][1]=1;ll numf3=Cal(ti,st);printf("%lld\n",Each(numc,numf1,numf2,numf3));}return 0;
}
//8 1 2 5 3
//7 1 2 5 3