常数矩阵快速幂+思维"/>
HDU2842 Chinese Rings 带常数矩阵快速幂+思维
先贴大佬博客Orz:
这道题有几点很巧妙:
1.拿掉第n个:先完成f(n-2),再拿掉第n环;然后放回前(n-2)(其实这也是f(n-2)),再加上f(n-1)
最终得到f(n)=f(n-1)+2*f(n-2)+1即为递推式。另:初始化f(1)=1,f(2)=2
2.矩阵快速幂中,遇到含有常数的式子,可以把A矩阵扩展为3*3的矩阵。
即最终得到下式:
| f(n) | | 1 2 1 | | f(n-1) |
| f(n-1) | = | 1 0 0 | * | f(n-2) |
| 1 | | 0 0 1 | | 1 |
中间的即为A矩阵,接下来用矩阵快速幂的板子就行了。附上AC代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)const int MOD=200907;
ll n;
typedef struct
{ll a[3][3];//矩阵大小
}mat;
mat c,res;mat mul(mat x,mat y,int n)
{mat cnt;memset(cnt.a,0,sizeof(cnt.a));for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)cnt.a[i][j]+=x.a[i][k]*y.a[k][j]%MOD;return cnt;
}
void pow()
{c.a[0][0]=1;c.a[0][1]=2;c.a[0][2]=1;c.a[1][0]=1;c.a[1][1]=0;c.a[1][2]=0;c.a[2][0]=0;c.a[2][1]=0;c.a[2][2]=1;memcpy(res.a,c.a,sizeof(c.a));n-=3;while(n>0){if(n&1)res=mul(res,c,3);c=mul(c,c,3);n=(n>>1);}
}
int main()
{while(cin>>n){if(n==0)break;else if(n==1)cout<<"1"<<endl;else if(n==2)cout<<"2"<<endl;else{pow();cout<<(res.a[0][0]*2+res.a[0][1]+res.a[0][2])%MOD<<endl;}}return 0;
}
更多推荐
HDU2842 Chinese Rings 带常数矩阵快速幂+思维
发布评论