@OceanEye8年前
07/7
10:18
12ms卡进前二十也是很人品……
第一问是二进制下的数位DP
第二问是个斐波那契数列……
然后分开来写一写就好了
【差点不会写矩阵乘法系列】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <cstdlib> #include <cmath> #define ll long long #define For(i,a,b) for(int i=a;i<=b;++i) #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; C=1; cc=getchar(); while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #undef p using namespace std; //dp[wei][is upper ?][0/1] //dp[i][0][1] -> dp[i-1][0][0] //dp[i][0][0] -> dp[i-1][0][0] + dp[i-1][0][1] //dp[i][1][1] -> dp[i-1][0][0] + dp[i-1][ //dp[i][1][1] -> dp[i-1][1][0] ll dp[70][2][2]; ll dfs(int a,int b,int c,const ll &d) { if(dp[a][b][c]) return dp[a][b][c]; if(a==0) return 1; #define p (d&(1LL<<(a-1))) if(!b) return dp[a][b][c]= (c==0?(dfs(a-1,0,1,d)+dfs(a-1,0,0,d)):dfs(a-1,0,0,d)) ; else { if(c) return p?dfs(a-1,0,0,d):dfs(a-1,1,0,d); else return p?dfs(a-1,0,0,d)+dfs(a-1,1,1,d):dfs(a-1,1,0,d); } #undef p } const int sqr[2][2]={{0,1},{1,1}}; int ksm(ll T) { // puts("SB"); #define mod 1000000007LL static ll a[2][2],b[2][2],c[2],ans[2]; a[0][0]=sqr[0][0]; a[0][1]=sqr[0][1]; a[1][0]=sqr[1][0]; a[1][1]=sqr[1][1]; ans[0]=0; ans[1]=1; for(;T;T>>=1) { if(T&1) { c[0]=ans[0]*a[0][0]+ans[1]*a[0][1]; c[1]=ans[0]*a[1][0]+ans[1]*a[1][1]; ans[0]=c[0]%mod; ans[1]=c[1]%mod; } for(int i=0;i<2;i++) for(int j=0;j<2;j++) { b[i][j]=0; for(int k=0;k<2;k++) b[i][j]+=a[i][k]*a[k][j]; } a[0][1]=b[0][1]%mod; a[0][0]=b[0][0]%mod; a[1][0]=b[1][0]%mod; a[1][1]=b[1][1]%mod; } return (int)ans[0]; } void Main() { static int t; static ll n; read(n); t=0; for(ll i=1;i<=n;i<<=1,t++); printf("%lld\n%d\n",dfs(t,1,0,n)-1,ksm(n+2)); } int main() { int T; |