AtCoder Beginner Contest 025 D問題 - 25個の整数

Source

AtCoder Beginner Contest 025
問題文

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

C++に変換後のコードはこちら

mint dp[33560000];
char vis[33560000];
int pt[25];
int mx[25], my[25];

mint solve(int mask, int k = 0){
  int f;
  if(vis[mask]) return dp[mask];
  f = (mask ^ ((1<<25)-1)) & pt[k];
  rep(i,25) if(f & 1<<i){
    if(mx[i] && ((mask >> (i-5)) + (mask >> (i+5))) & 1 == 1) continue;
    if(my[i] && ((mask >> (i-1)) + (mask >> (i+1))) & 1 == 1) continue;
    dp[mask] += solve(mask | (1<<i), k + 1);
  }
  vis[mask] = 1;
  return dp[mask];
}

{
  int x;
  rep(i,25) pt[i] = (1<<25) - 1;
  rep(i,25){
    rd(x--);
    if(x >= 0){
      rep(j,25) if(pt[j] & 1<<i) pt[j] ^= 1<<i;
      pt[x] = 1<<i;
    }
  }
  rep(i,1,4) rep(j,5) mx[5i+j] = 1;
  rep(i,5) rep(j,1,4) my[5i+j] = 1;
  vis[(1<<25)-1] = 1;
  dp[(1<<25)-1] = 1;
  wt(solve(0));
}

Current time: 2024年04月20日00時13分12秒
Last modified: 2019年09月21日11時55分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC025 ABC_D
トップページに戻る

Logged in as: unknown user (not login)