{"id":149,"date":"2010-03-12T18:15:00","date_gmt":"2010-03-12T10:15:00","guid":{"rendered":"http:\/\/localhost\/?p=149"},"modified":"2010-03-12T18:15:00","modified_gmt":"2010-03-12T10:15:00","slug":"hnoi2008_plainly_troubles","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=149","title":{"rendered":"[HNOI2008]\u660e\u660e\u7684\u70e6\u607c"},"content":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem<\/a>
\u8fd9\u9053\u9898\u5f88\u6709\u610f\u601d\u554a\u3002\u3002\u5c31\u662f\u8bf4\u4e00\u68f5\u6811\u5bf9\u4e00\u4e9b\u9876\u70b9\u7684\u5ea6\u6570\u6709\u8981\u6c42\u4e00\u4e9b\u6ca1\u6709\uff0c\u8ba9\u4f60\u6c42\u8fd9\u6837\u7684\u6811\u7684\u5ea6\u6570\u3002
\u6211\u4e00\u5f00\u59cb\u60f3DP\u8111\u5b50\u90fd\u7206\u4e86\u4e5f\u6ca1\u60f3\u51fa\u6765\u3002\u3002\u6700\u540e\u60f3\u5230Prufer Code\u3002\u3002\u7136\u540e\u5c31\u660e\u767d\u4e86\u3002\u3002
Prufer Code\u662f\u628a\u6bcf\u68f5n\u70b9\u7684\u6811\u5bf9\u5e94\u5230\u957f\u5ea6\u4e3an-2\uff0c\u6570\u57281-n\u4e4b\u95f4\u7684\u6570\u5217\u3002\u3002\u5176\u4e2d\u4e00\u4e2a\u5ea6\u6570\u4e3ad\u7684\u70b9\u51fa\u73b0d-1\u6b21\u3002\u3002
wiki\u4e0a\u7684\u8bf4\u660e:en.wikipedia.org\/wiki\/Prufer_code<\/a>
\u8fd9\u5c31\u662f\u5173\u952e\u3002\u6240\u4ee5\u95ee\u9898\u5c31\u8f6c\u5316\u6210\u6c42\u8fd9\u6837\u7684\u6570\u5217\u7684\u6570\u76ee\u4e86\u3002\u3002\u8fd9\u7528\u591a\u91cd\u96c6\u7684\u516c\u5f0f\u5f88\u65b9\u4fbf\uff0c\u5c31\u4e0d\u591a\u8bf4\u4e86\u3002\u3002
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000;
int n;
vector<int> Prime;
typedef vector<int>::iterator it;
int D[maxn],S=0,noLimit=0;
bool isPrime(int x)
{
if(x==2) return true;
if(x\/2==0) return false;
for(int i=3;i*i<=x;i+=2)
if(x%i==0) return false;
return true;
}
void getPrime()
{
for(int i=2;i<=n;i++)
if(isPrime(i)) Prime.pb(i);
}
void init()
{
cin>>n;
rep(i,n)
{
cin>>D[i];
if(D[i]>0)
S+=D[i]-1;
else
noLimit++;
}
}
struct BigInt
{
int H[400];
BigInt(){memset(H,0,sizeof(H));}
void mul(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x\/=Prime[i],H[i]++;
}
void div(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x\/=Prime[i],H[i]–;
}
};
ostream& operator<<(ostream&out,const BigInt&x)
{
static int Hp[100000],last;
memset(Hp,0,sizeof(Hp));Hp[last=0]=1;
rep(i,Prime.size())
{
rep(j,x.H[i])
{
int o=Prime[i],d=0;
rep(k,last+1)
{
d+=Hp[k]*o;
Hp[k]=d%10;
d\/=10;
}
while(d) Hp[++last]=d%10,d\/=10;
}
}
for(int i=last;i>=0;–i)out<<Hp[i];
return out;
}
void work()
{
if(S>n-2){cout<<0<<endl;return;}
if(noLimit==0&&S<n-2){cout<<0<<endl;return;}
getPrime();
BigInt ans;
for(int i=1;i<=n-2;i++)
ans.mul(i);
rep(i,n)
{
if(D[i]>0)
for(int j=1;j<=D[i]-1;j++)
ans.div(j);
}
for(int i=1;i<=n-2-S;i++)
ans.div(i);
rep(i,n-2-S) ans.mul(noLimit);
cout<<ans<<endl;
}
int main()
{
\/\/freopen("in","r",stdin);
init();
work();
}
PS\u3002\u3002o(\ufe36\ufe3f\ufe36)o \u8fd9\u4e2aOJ\u4e0d\u80fd\u7528Java\u3002\u8fd8\u5f97\u81ea\u5df1\u5199\u9ad8\u7cbe\u5ea6\u56e7\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"

61.187.179.132:8080\/JudgeOnline\/showproblem\u8fd9\u9053\u9898\u5f88\u6709\u610f\u601d\u554a\u3002\u3002\u5c31\u662f\u8bf4\u4e00\u68f5\u6811\u5bf9\u4e00\u4e9b\u9876\u70b9\u7684\u5ea6\u6570\u6709\u8981\u6c42\u4e00\u4e9b\u6ca1\u6709\uff0c\u8ba9\u4f60\u6c42\u8fd9\u6837\u7684\u6811\u7684\u5ea6\u6570\u3002\u6211\u4e00\u5f00\u59cb\u60f3DP\u8111\u5b50\u90fd\u7206\u4e86\u4e5f\u6ca1\u60f3\u51fa\u6765\u3002\u3002\u6700\u540e\u60f3\u5230Prufer Code\u3002\u3002\u7136\u540e\u5c31\u660e\u767d\u4e86\u3002\u3002Prufer Code\u662f\u628a\u6bcf\u68f5n\u70b9\u7684\u6811\u5bf9\u5e94\u5230\u957f\u5ea6\u4e3an-2\uff0c\u6570\u57281-n\u4e4b\u95f4\u7684\u6570\u5217\u3002\u3002\u5176\u4e2d\u4e00\u4e2a\u5ea6\u6570\u4e3ad\u7684\u70b9\u51fa\u73b0d-1\u6b21\u3002\u3002wiki\u4e0a\u7684\u8bf4\u660e:en.wikipedia.org\/wiki\/Prufer_code\u8fd9\u5c31\u662f\u5173\u952e\u3002\u6240\u4ee5\u95ee\u9898\u5c31\u8f6c\u5316\u6210\u6c42\u8fd9\u6837\u7684\u6570\u5217\u7684\u6570\u76ee\u4e86\u3002\u3002\u8fd9\u7528\u591a\u91cd\u96c6\u7684\u516c\u5f0f\u5f88\u65b9\u4fbf\uff0c\u5c31\u4e0d\u591a\u8bf4\u4e86\u3002\u3002Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=1000;int n;vector<int> Prime;typedef vector<int>::iterator it;int D[maxn],S=0,noLimit=0;bool isPrime(int x){ if(x==2) return true; if(x\/2==0) return false; for(int i=3;i*i<=x;i+=2) if(x%i==0) return false; return true;}void getPrime(){ for(int i=2;i<=n;i++) if(isPrime(i)) Prime.pb(i);}void init(){ cin>>n; rep(i,n) { cin>>D[i]; if(D[i]>0) S+=D[i]-1; else noLimit++; }}struct BigInt{ int H[400]; BigInt(){memset(H,0,sizeof(H));} void mul(int x) { […]<\/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\/149"}],"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=149"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/149\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}