D. Magic Gems
题意
长度为n的01串0的个数是m的倍数，而且每m个0都是连续的方案数。
1≤n≤10181 \leq n \leq 10^{18}1≤n≤1018
2≤m≤1002 \leq m \leq 1002≤m≤100
做法
可以看到n很大，我们首先想n很小的时候怎么做，我们用dp[i]表示长度为i的串的合法方案数，第i位放1的方案数为dp[i-1]，第i位放0的方案数位dp[i-m],所以得到转移方程dp[i]=dp[i-m]+dp[i-1],由于m很小，很显然可以通过矩阵快速幂加速这个转移。
时间复杂度O(m3?log(n))O(m^3*log(n))O(m3?log(n))
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int Mod=1000000007;
void add(ll &x,ll y)
{
x+=y;if(x>=Mod) x%=Mod;
}
struct mat
{
ll jz[105][105];
};
int m;
mat mat_mul(mat x,mat y)
{
mat res;memset(res.jz,0,sizeof(res.jz));for(int i=0;i<m;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)add(res.jz[i][j],x.jz[i][k]*y.jz[k][j]);return res;
}
ll power_mod (ll P)//.res是系数矩阵,ans是变换矩阵!!左->ans,右->res.!!
{
mat ans,res;for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
ans.jz[i][j]=0;res.jz[i][j]=0;}}for(int i=0;i<=m-2;i++) res.jz[i+1][i]=1;res.jz[0][m-1]=1;res.jz[m-1][m-1]=1;for(int i=0;i<=m-1;i++) ans.jz[0][i]=1;while(P>0){
if(P&1) ans=mat_mul(ans,res);//所以应该答案矩阵在左ans,res);P=P>>1;res=mat_mul(res,res);}return (ans.jz[0][m-1]+Mod)%Mod;//返回指定位置元素
}
int main()
{
ll n;scanf("%lld%d",&n,&m);if(n<=m-1) printf("1\n");else printf("%lld\n",power_mod(n-m+1));return 0;
}