18.09.21 模拟赛 T1.
这实际上是 zhx 出的增强版.
考试的时候写了 15 分暴力, 没推出来式子......
先看一下题:
洛谷 P4451 传送门 https://www.luogu.org/problemnew/show/P4451
bzoj 2173 传送门
题面是一样的.
只不过, 网上那道题的数据范围好小啊.
所以出题人 zhx 大佬把 n 的范围改成了 1^18, 把取模数改成了 1^18+7.
式子: f[x]=2*f[x-1]+f[x-2]
矩阵乘法优化:
f[k-1] f[k-2] 乘上 2 1 等于 f[k] f[k-1]
0 0 1 0 0 0
再写个快速乘就行了.
这么简单的题我居然没切...... 面壁.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define ll long long
- using namespace std;
- ll n;
- ll m=(ll)(1e18)+7;
- struct matrix
- {
- ll a[2][2];
- }f,g;
- ll multi(ll q,ll w)
- {
- ll ret=0;
- while(w)
- {
- if(w&1)ret=(ret+q)%m;
- q=(q+q)%m;
- w>>=1;
- }
- return ret;
- }
- matrix multi(matrix q,matrix w)
- {
- matrix e;
- for(int i=0;i<=1;i++)
- {
- for(int j=0;j<=1;j++)
- {
- e.a[i][j]=0;
- for(int k=0;k<=1;k++)
- {
- e.a[i][j]=(e.a[i][j]+multi(q.a[i][k],w.a[k][j]))%m;
- }
- }
- }
- return e;
- }
- matrix ksm(matrix b,ll p)
- {
- matrix ret=b;
- p--;
- while(p)
- {
- if(p&1)ret=multi(ret,b);
- b=multi(b,b);
- p>>=1;
- }
- return ret;
- }
- int main()
- {
- freopen("RSA.in","r",stdin);
- freopen("R5A.out","w",stdout);
- scanf("%I64d",&n);
- f.a[0][0]=0,f.a[0][1]=1;
- g.a[0][0]=2;
- g.a[0][1]=g.a[1][0]=1;
- g=ksm(g,n);
- f=multi(f,g);
- printf("%I64d",f.a[0][0]);
- fclose(stdin);
- fclose(stdout);
- return 0;
- }
[国家集训队] 整数的 lqp 拆分
来源: http://www.bubuko.com/infodetail-2776314.html