这题竟然和5004 m=1时几乎一样.....
先不考虑至少放两个，方案数和那题一样，再减掉不放和放一个的，共n+1种（把棋子放在格子中n为格子数
矩乘斐波那契
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e18+9; ll n,mod; ll mul(ll a,ll b){ ll ans=0; while(b){ if(b&1)ans=(ans+a)%mod; a=(a<<1)%mod;b>>=1; } return ans; } struct node{ ll a[5][5]; node(){memset(a,0,sizeof(a));} node operator *(const node&t)const{ node ans; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) (ans.a[i][j]+=mul(a[i][k],t.a[k][j]))%=mod; return ans; } }ans,p; node operator ^(node x,ll b){ node ans; ans.a[1][1]=1;ans.a[2][2]=1; while(b){ if(b&1)ans=ans*x; x=x*x; b>>=1; } return ans; } ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1)ans=mul(ans,a); a=mul(a,a); b>>=1; } return ans; } int main(){ scanf("%d%d",&n,&mod);n++; if(n<=3){ if(n==1)cout<<0; if(n==2)cout<<0; if(n==3)cout<<1; return 0; } ans.a[1][1]=1;ans.a[1][2]=1; p.a[1][1]=1;p.a[1][2]=1;p.a[2][1]=1; p=p^(n);ans=ans*p; ll aa=((ans.a[1][1]-n-1)%mod+mod)%mod; aa=qpow(aa,n); printf("%lld",aa%mod); }