SRM 427 Div1 Hard

問題概要

n個の整数a[i]が与えられる。
これを、任意の隣り合う二つの数a[k],a[k+1]について(a[k]-a[k+1])%p==0が成り立たないように並べ替える場合の数をmod 1234567891で求めよ。

制約条件

n≦30
-10^6≦a[i]≦10^6
p≦1000

方針

nが30と大きいので愚直にビットDPすることはできないので工夫する必要がある。
まず、全ての数はmod pで考えて良い。

mod pで数が
2 2 3 4のようになったときに、
その個数のvectorを{2,1,1}とする。

このvectorをソートしたものと、直前の数（＝禁止するグループの数）を状態とするDPをすると、状態数が減って解ける。
この状態からは次のような状態ができる。
{1,1,1}で個数1のグループが禁止。
{2,1}で個数0のグループが禁止。

禁止の個数のグループが複数ある場合、
全てのグループは対照的なので、一つだけのグループを禁止すると考えて問題ない。

ソースコード

map<pair<vi,int>,int> dp;
int go(vi v,int prev){
  int n=v.size();

  sort(all(v),greater<int>());
  if(v[n-1]==0)v.pop_back(), n--;
  
  if(n==0)return 1;
  if(dp.count(mp(v,prev)))return dp[mp(v,prev)];

  ll ret=0;
  rep(i,n){
    if(v[i]==prev&&(i==0||v[i]!=v[i-1]))continue;
    v[i]--;
    ret+=(ll)(v[i]+1)*go(v,v[i])%mod;
    v[i]++;
  }
  return dp[mp(v,prev)]=int(ret%mod);
}
class PSequence {
  public:
  int count(vector <int> S, int p) {
    dp.clear();

    int s[1000]={};
    rep(i,S.size())s[(S[i]%p+p)%p]++;
    sort(s,s+1000);
    vi v;
    rep(i,1000)if(s[i])v.pb(s[i]);
    return go(v,0);
  }
};