建设网站专业公司吗,有个虚拟服务器建设网站,艺术品拍卖网站源码php,崇左北京网站建设链接#xff1a;http://codeforces.com/problemset/problem/821/E 分析#xff1a;由于有边界而且不同段边界还不同#xff0c;直接算是不行的。。k是1e18#xff0c;dp也不行。。用一个16维的向量表示某一列16个位置可能的种类数#xff0c;到下一列的转移矩阵容易得到http://codeforces.com/problemset/problem/821/E 分析由于有边界而且不同段边界还不同直接算是不行的。。k是1e18dp也不行。。用一个16维的向量表示某一列16个位置可能的种类数到下一列的转移矩阵容易得到而且在同一段里转移矩阵一样直接用快速幂算出这一段结束的向量然后继续推下一段结束的向量。注意特殊情况的处理。 1 #includeiostream2 #includecstring3 using namespace std;4 typedef long long ll;5 const int maxn105,p1e97;6 ll a[maxn],b[maxn],c[maxn];7 ll m[16][16],v[16];8 void initm(ll k){9 for(int i0;i16;i)
10 for(int j0;j16;j)
11 m[i][j]0;
12 m[0][0]1;m[0][1]1;
13 for(int i1;ik;i){
14 m[i][i-1]m[i][i]m[i][i1]1;
15 }
16 if(k0){
17 m[k][k]1;m[k][k-1]1;
18 }else{
19 m[0][1]0;
20 }
21 }
22 void Copy(ll a[16][16],ll b[16][16]){
23 for(int i0;i16;i)
24 for(int j0;j16;j)
25 a[i][j]b[i][j];
26 }
27 void multiply(ll ma[16][16],ll mb[16][16],ll ans[16][16]){
28 ll a[16][16],b[16][16];
29 Copy(a,ma);Copy(b,mb);
30 for(int i0;i16;i){
31 for(int j0;j16;j){
32 ans[i][j]0;
33 for(int k0;k16;k)
34 ans[i][j](ans[i][j]a[i][k]*b[k][j])%p;
35 }
36 }
37 }
38 void print(ll a[16][16]){
39 for(int i0;i16;i){
40 for(int j0;j16;j)
41 couta[i][j] ;
42 coutendl;
43 }
44 }
45 void qpow(ll a[16][16],ll n,ll ans[16][16]){
46 ll k1,y[16][16];
47 for(int i0;i16;i){
48 for(int j0;j16;j)
49 ans[i][j]0;
50 ans[i][i]1;
51 }
52 Copy(y,a);
53 while(k){
54 if(kn){
55 multiply(ans,y,ans);
56 //print(ans);
57 }
58 multiply(y,y,y);
59 k1;
60 }
61 }
62 void Update(ll n,int h){
63 initm(h);
64 ll M[16][16],v0[16];
65 memset(v0,0,sizeof(v0));
66 qpow(m,n,M);
67 for(int i0;i16;i){
68 for(int j0;j16;j){
69 v0[i](v0[i]v[j]*M[i][j])%p;
70 }
71 }
72 for(int i0;i16;i)v[i]v0[i];
73 }
74 int main(){
75 int n;
76 ll aim;
77 memset(v,0,sizeof(v));
78 v[0]1;
79 cinnaim;
80 for(int i0;in;i){
81 cina[i]b[i]c[i];
82 if(in-1)b[i]aim;
83 Update(b[i]-a[i],c[i]);
84 }
85 coutv[0]endl;
86 return 0;
87 } 转载于:https://www.cnblogs.com/7391-KID/p/7082055.html
