{"id":212,"date":"2010-04-04T13:53:00","date_gmt":"2010-04-04T05:53:00","guid":{"rendered":"http:\/\/localhost\/?p=212"},"modified":"2010-04-04T13:53:00","modified_gmt":"2010-04-04T05:53:00","slug":"topcoder_srm_466_div_1_1000","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=212","title":{"rendered":"TopCoder SRM 466 DIV 1 1000"},"content":{"rendered":"

\u6655\u3002\u3002\u8fd9\u9053\u9898\u76ee\u5176\u5b9e\u4e0d\u7b97\u592a\u96be\u3002\u5f53\u65f6\u8111\u5b50\u5c0f\u4e86\u56e7\u3002\u3002
\u53ea\u8981dp\u5c31\u53ef\u4ee5\u4e86\u3002\u5b9e\u9645\u4e0a\u7531\u4e8e\u9ed1\u8272\u7684\u6700\u591a\u53ea\u67098\u4e2a\uff0c\u90a3\u4e48\u72b6\u6001\u5c31\u662f\uff08usedRow\uff0cusedCol\uff0cLeftRow,LeftCol\uff09.\u5176\u4e2d\u6700\u540e\u4e00\u4e2a\u6ca1\u5fc5\u8981\u50a8\u5b58\uff0c\u662f\u6709\u524d\u4e09\u4e2a\u552f\u4e00\u786e\u5b9a\u7684\u3002\u3002
\u9996\u5148\u628a\u9ed1\u8272\u7684\u5168\u5f80\u5de6\u4e0a\u89d2\u6254\u3002\u3002\u90a3\u4e48\u5de6\u4e0a\u89d2\u7684\u201c\u9ed1\u5757\u201d\u6700\u591a\u53ea\u67098*8\u5927\u5c0f\u3002
usedRow\u5c31\u662f\u9ed1\u5757\u7684row\u7684\u5360\u7528\u60c5\u51b5\uff0cusedCol\u5c31\u662f\u9ed1\u5757\u7684Col\u5360\u7528\u7684\u60c5\u51b5\uff0cLeftRow\u5c31\u5269\u4e0b\u7684\u6ca1\u88ab\u5360\u7528\u7684\u767d\u8272Row\uff0cLeftCol\u4e5f\u4e00\u6837\uff0c\u7136\u540eDp\u5c31\u53ef\u4ee5\u4e86\u56e7\u3002\u3002\u6700\u6076\u5fc3\u7684\u662f\u5982\u679c\u8fb9\u754c\u60c5\u51b5\u5c31\u662f\u6ca1\u6709\u4efb\u4f55\u540e\u7ee7\u7684\u8bdd\u7b54\u6848\u5e94\u8be5\u662f1\uff0c\u4f46\u4e0d\u80fd\u6839\u636e\u7b54\u6848\u662f\u5426\u4e3a0\u5224\u65ad\uff0c\u56e0\u4e3a\u5b83\u4e5f\u53ef\u80fd\u6070\u597d\u662f10000000007\u7684\u500d\u6570\u989d\u554a\u56e7\u3002\u3002\u597d\u5427code\u592augly\u4e86\u56e7\u3002\u3002
\u624b\u673a\u4e70\u4e86\u5c45\u7136\u662f\u5c71\u5be8\u7684\u6655\u6b7b\u3002\u3002\u73b0\u5728\u9ad8\u4eff\u592a\u591a\u4e86\u56e7\u3002\u3002
Code\uff1a
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef long long ll;
typedef unsigned long long ull;<\/p>\n

class DrawingBlackCrosses {
public:
int count(vector <string>);
};
const int maxn=20;
const ll mod=1000000007;
bool a[maxn][maxn];
int bn,bm,n,m;
ll Dp[maxn+1][1<<8][1<<8];
bool S[maxn+1][1<<8][1<<8]={0};
ll dfs(int ur,int uc,int ln,int lm)
{
ll&x=Dp[ln][ur][uc];
if(S[ln][ur][uc]) return x;
S[ln][ur][uc]=true;x=0;bool ok=false;
rep(i,bn)rep(j,bm)if((ur&(1<<i))==0&&(uc&(1<<j))==0&&!a[i][j])
x+=dfs(ur^(1<<i),uc^(1<<j),ln,lm),x%=mod,ok=true;
if(lm>0)rep(i,bn)if((ur&(1<<i))==0) x+=dfs(ur^(1<<i),uc,ln,lm-1)*lm,x%=mod,ok=true;
if(ln>0)rep(i,bm)if((uc&(1<<i))==0)x+=dfs(ur,uc^(1<<i),ln-1,lm)*ln,x%=mod,ok=true;
if(ln>0&&lm>0)x+=dfs(ur,uc,ln-1,lm-1)*ln*lm,x%=mod,ok=true;
if(!ok)x=1;
return x;
}
int DrawingBlackCrosses::count(vector <string> field) {
vector<string>T(all(field)),A;
sort(all(T));
reverse(all(T));
rep(i,T[0].size())
{
string a="";
rep(j,T.size())
{
a+=T[j][i];
}
A.pb(a);
}
sort(all(A));
reverse(all(A));bn=bm=0;n=A.size();m=A[0].size();
rep(i,n)rep(j,m)
{
a[i][j]=A[i][j]==’B’;
if(a[i][j]) bn>?=i+1,bm>?=j+1;
}
return dfs(0,0,n-bn,m-bm);
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u6655\u3002\u3002\u8fd9\u9053\u9898\u76ee\u5176\u5b9e\u4e0d\u7b97\u592a\u96be\u3002\u5f53\u65f6\u8111\u5b50\u5c0f\u4e86\u56e7\u3002\u3002\u53ea\u8981dp\u5c31\u53ef\u4ee5\u4e86\u3002\u5b9e\u9645\u4e0a\u7531\u4e8e\u9ed1\u8272\u7684\u6700\u591a\u53ea\u67098\u4e2a\uff0c\u90a3\u4e48\u72b6\u6001\u5c31\u662f\uff08usedRow\uff0cusedCol\uff0cLeftRow,LeftCol\uff09.\u5176\u4e2d\u6700\u540e\u4e00\u4e2a\u6ca1\u5fc5\u8981\u50a8\u5b58\uff0c\u662f\u6709\u524d\u4e09\u4e2a\u552f\u4e00\u786e\u5b9a\u7684\u3002\u3002\u9996\u5148\u628a\u9ed1\u8272\u7684\u5168\u5f80\u5de6\u4e0a\u89d2\u6254\u3002\u3002\u90a3\u4e48\u5de6\u4e0a\u89d2\u7684\u201c\u9ed1\u5757\u201d\u6700\u591a\u53ea\u67098*8\u5927\u5c0f\u3002usedRow\u5c31\u662f\u9ed1\u5757\u7684row\u7684\u5360\u7528\u60c5\u51b5\uff0cusedCol\u5c31\u662f\u9ed1\u5757\u7684Col\u5360\u7528\u7684\u60c5\u51b5\uff0cLeftRow\u5c31\u5269\u4e0b\u7684\u6ca1\u88ab\u5360\u7528\u7684\u767d\u8272Row\uff0cLeftCol\u4e5f\u4e00\u6837\uff0c\u7136\u540eDp\u5c31\u53ef\u4ee5\u4e86\u56e7\u3002\u3002\u6700\u6076\u5fc3\u7684\u662f\u5982\u679c\u8fb9\u754c\u60c5\u51b5\u5c31\u662f\u6ca1\u6709\u4efb\u4f55\u540e\u7ee7\u7684\u8bdd\u7b54\u6848\u5e94\u8be5\u662f1\uff0c\u4f46\u4e0d\u80fd\u6839\u636e\u7b54\u6848\u662f\u5426\u4e3a0\u5224\u65ad\uff0c\u56e0\u4e3a\u5b83\u4e5f\u53ef\u80fd\u6070\u597d\u662f10000000007\u7684\u500d\u6570\u989d\u554a\u56e7\u3002\u3002\u597d\u5427code\u592augly\u4e86\u56e7\u3002\u3002\u624b\u673a\u4e70\u4e86\u5c45\u7136\u662f\u5c71\u5be8\u7684\u6655\u6b7b\u3002\u3002\u73b0\u5728\u9ad8\u4eff\u592a\u591a\u4e86\u56e7\u3002\u3002Code\uff1a#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()const int inf=~0U>>1;using namespace std;typedef pair<int,int> ii;typedef vector<int> vi;typedef vi::iterator vit;typedef long long ll;typedef unsigned long long ull; class DrawingBlackCrosses {public: int count(vector <string>);};const int maxn=20;const ll […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/212"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=212"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/212\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}