这道题很神啊……
神爆了……
思路大家应该看别的博客已经知道了，但大部分用的插头DP。我加了预处理，没用插头DP，一行一行来，速度还挺快。
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <cmath> #define N 100100 #define M 50 #define yu 1000000001 #define inf 1<<29 using namespace std; int n; long long ans=1; long long f[2][N/M]={0}; int keneng[N/M],kenengnum; int sushu[N],sushunum; void make_sushu(int limit) // 这里不是筛素数，而是把不是2,3的倍数的筛出来 { // 如果筛素数，25不是素数，但是5的矩阵不能包含25 int i,j,k; int vis[N]={0}; sushunum=0; for (i=1;i<=limit;i++) if (i%2!=0&&i%3!=0) sushu[++sushunum]=i; } bool shifou(int now) // 预处理的判断，判断是否有两个1相连 { // 即是否取连续的两个数 int i,j,k; i=now&1; now>>=1; while (now!=0) { j=now&1; if (i==j&&i&&j) return false; i=j; now>>=1; } return true; } void chuli(int limit) //预处理，把可以选的状态存起来，省时间 { int i,j,k; int maxn=1; kenengnum=0; for (i=1;i<=limit;i++) maxn*=2; for (i=0;i<maxn;i++) { if (shifou(i)) { keneng[kenengnum++]=i; } } } int pd_long(int x) // 由于矩阵每一行长度不同，所以预处理某些不能用 { // 这个判断每一行长度 int i=1,zanshi=0; while (i<=x) { zanshi++; i*=3; } return zanshi; } long long make_juzhen(int now) { int i,j,k,x=1,y,z; int limit,lnow,lnowbefore=inf; limit=pd_long(n/now); chuli(limit); f[0][0]=1; for (i=1;x*now<=n;i++,x*=2) { memset(f[i%2],0,sizeof(f[i%2])); lnow=pd_long(n/now/x); // 当前行的长度 for (j=0;j<kenengnum;j++) { if (keneng[j]>>lnow>0) //如果有选超过当前行长度的，不选 { f[i%2][j]=0; continue; } for (k=0;k<kenengnum;k++) // 和上一行比较，是否有相连的1选了 { if (keneng[k]>>lnowbefore>0) // 上一行状态不能超过上一行长度 continue; if (keneng[j]&keneng[k]) continue; f[i%2][j]+=f[(i+1)%2][k]; f[i%2][j]%=yu; } } lnowbefore=lnow; // 上一行长度 } return (f[(i+1)%2][0]+f[(i+1)%2][1])%yu; //最后一行一定只有一个，答案只有这两种情况加起来，最后一个选或不选 } int main() { int i,j,k,x,y,z; cin>>n; make_sushu(n); for (i=1;i<=sushunum;i++) { ans*=make_juzhen(sushu[i]); ans%=yu; } cout<<ans<<endl; }