首页 > 代码库 > BZOJ 4824: [Cqoi2017]老C的键盘
BZOJ 4824: [Cqoi2017]老C的键盘
Description
上一题弱化版,\(n\leqslant 100\)
Solution
树形DP.
Code
/************************************************************** Problem: 4824 User: BeiYu Language: C++ Result: Accepted Time:188 ms Memory:18580 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;typedef pair<int,int> pr;const int N = 1050;const LL p = 1e9+7; #define mpr make_pair#define x first#define y second int T,n;vector<pr> h[N];LL fac[N<<1],ifac[N<<1];LL f[N][N],g[N][N],sz[N],tmp[N]; LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }void Add(LL &x,LL y) { x=(x+y)%p; }void init(int n) { fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p; ifac[n]=Pow(fac[n],p-2),ifac[0]=1; for(int i=n-1;i;--i) ifac[i]=ifac[i+1]*(i+1)%p;}LL C(int n,int m) { return n<m?0:fac[n]*ifac[m]%p*ifac[n-m]%p; }void AddEdge(int fr,int to,int v) { h[fr].push_back(mpr(to,v)); }void clr() { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); for(int i=0;i<N;i++) h[i].clear();}void DFS(int u,int fa) { sz[u]=1,f[u][1]=1; for(int t=0,v;t<(int)h[u].size();t++) if((v=h[u][t].x)!=fa){ DFS(v,u); for(int i=0;i<=sz[u]+sz[v];i++) tmp[i]=0; if(h[u][t].y) for(int i=1;i<=sz[u];i++) for(int j=1;j<=sz[v];j++) Add(tmp[i+j],f[u][i]*g[v][j]%p*C(i+j-1,j)%p*C(sz[u]+sz[v]-i-j,sz[v]-j)%p); else for(int i=1;i<=sz[u];i++) for(int j=0;j<=sz[v];j++) Add(tmp[i+j],f[u][i]*(g[v][sz[v]]-g[v][j]+p)%p*C(i+j-1,j)%p*C(sz[u]+sz[v]-i-j,sz[v]-j)%p); sz[u]+=sz[v]; for(int i=1;i<=sz[u];i++) f[u][i]=tmp[i]; } for(int i=1;i<=sz[u];i++) g[u][i]=(g[u][i-1]+f[u][i])%p; /* cout<<"------"<<endl; cout<<u<<" "<<fa<<" "<<sz[u]<<endl; for(int i=1;i<=sz[u];i++) cout<<f[u][i]<<" ";cout<<endl;*/}char s[N];int main() { for(T=1,init(2000);T--;) { clr();scanf("%d",&n); scanf("%s",s+2); for(int i=2;i<=n;i++) { if(s[i]==‘<‘) AddEdge(i/2,i,0),AddEdge(i,i/2,1); else AddEdge(i/2,i,1),AddEdge(i,i/2,0); }DFS(1,1); LL ans=0; for(int i=1;i<=n;i++) Add(ans,f[1][i]); printf("%lld\n",ans); }return 0;}
BZOJ 4824: [Cqoi2017]老C的键盘
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。