题目链接

题解

构造矩阵的思路真的没想到

选\(x\)就不能选\(2x\)和\(3x\)，会发现实际可以转化为矩阵相邻两项

\[\begin{matrix}1 & 3 & 9 & 27 & ... \\2 & 6 & 18 & 54 & ... \\4 & 12 & 36 & 108 & ... \\8 & 24 & 72 & 216 & ... \\ ... & ... &... &... &... \\ \end{matrix}\]

相当于选这样的矩阵中不相邻的若干项的方案数

我们取每一个不是\(2\)和\(3\)的倍数的数作为矩阵左上角

行数和列数都很小，可以状压\(dp\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long intusing namespace std;const int maxn = 20,maxm = (1 << 12),INF = 1000000000,P = 1000000001;int f[maxn][maxm];int N,n,cnt[maxn];int ill[maxm],ans = 1;void init(){ int t = 3; for (int s = 0; s < maxm; s++){ for (int i = 0; i <= 10; i++) if (((s & (t << i)) >> i) == t){ ill[s] = true; break; } }}void dp(int x){ for (n = 0; x <= N; x *= 2){ cnt[++n] = 0; int t = x; while (t <= N) cnt[n]++,t *= 3; } for (int i = 1; i <= n; i++) for (int s = 0; s < (1 << cnt[i]); s++) f[i][s] = 0; for (int s = 0; s < (1 << cnt[1]); s++) if (!ill[s]) f[1][s] = 1; for (int i = 2; i <= n; i++) for (int s = 0; s < (1 << cnt[i]); s++){ if (ill[s]) continue; for (int e = 0; e < (1 << cnt[i - 1]); e++){ if (ill[e]) continue; if (!(s & e)){ f[i][s] = (f[i][s] + f[i - 1][e]) % P; } } } int re = 0; for (int s = 0; s < (1 << cnt[n]); s++) re = (re + f[n][s]) % P; ans = 1ll * ans * re % P;}int main(){ init(); scanf("%d",&N); for (int i = 1; i <= N; i++){ if (i % 2 == 0 || i % 3 == 0) continue; dp(i); } printf("%d\n",ans); return 0;}