「NOI2015」壽司晚宴 （DP）

#include<bits/stdc++.h>
#define cs const
using namespace std;
typedef long long ll;
cs int N = 505, M = 1 << 8;
ll Mod;
ll add(ll a, ll b){ return a + b >= Mod ? a + b - Mod : a + b; }
ll dec(ll a, ll b){ return a - b < 0 ? a - b + Mod : a - b; }
ll mul(ll a, ll b){ return (a*b - (ll)((long double)a/b*Mod)*Mod + Mod) % Mod; }
void Add(ll &a, ll b){ a = add(a, b); }
int n, prim[N], pc, mx, id[N]; bool isp[N];
vector<int> G[N];
ll dp[M][M];
void sieve(int n){
  for(int i = 2; i <= n; i++){
    if(!isp[i]) prim[++pc] = i, id[i] = pc;
    for(int j = 1; j <= pc && i * prim[j] <= n; ++j){
      isp[prim[j] * i] = true; if(i % prim[j] == 0) break;
    }
  }
}
void trans(int x){
  int S = 0;
  for(int i = 1; i <= 8; i++)
  if(x % prim[i] == 0){ S|=(1<<i-1); while(x%prim[i]==0) x/=prim[i]; }
  G[id[x]].push_back(S); mx = max(mx, id[x]);
}
int main(){
  cin >> n >> Mod; sieve(N-5);
  for(int i = 2; i <= n; i++) trans(i);
  dp[0][0] = 1;
  int S = (1 << 8);
  for(int k : G[0])
  for(int i = S-1; ~i; i--)
  for(int j = S-1; ~j; j--) if(!(i&j)) {
    if(!(k&i)) Add(dp[i][j|k],dp[i][j]);
    if(!(k&j)) Add(dp[i|k][j],dp[i][j]);
  }
  for(int t = 9; t <= mx; t++){
    static ll g[M][M], h[M][M];
    memcpy(g, dp, sizeof(dp));
    memcpy(h, dp, sizeof(dp));
    for(int k : G[t]) 
    for(int i = S-1; ~i; i--)
    for(int j = S-1; ~j; j--) if(!(i&j)){
      if(!(k&j)) Add(g[i|k][j],g[i][j]);
      if(!(k&i)) Add(h[i][j|k],h[i][j]);
    }
    for(int i = 0; i < S; i++)
    for(int j = 0; j < S; j++) if(!(i&j))
    dp[i][j] = dec(add(g[i][j],h[i][j]),dp[i][j]);
  }
  ll ans = 0;
  for(int i = 0; i < S; i++)
  for(int j = 0; j < S; j++) if(!(i&j)&&dp[i][j]) Add(ans, dp[i][j]);
  cout << ans; return 0;
}