企业官网建设流程全解析

1. 有向无环图(使用状压dp)

例题(L-Lazy Shuffling_2026牛客暑期多校训练营2)

#include <bits/stdc++.h> #define int long long using namespace std; const int N = 200010,mod=998244353; void add(int &x,int y) { x=(x+y+mod)%mod; } void solve() { int n; cin>>n; vector<int> p(n),vis(n); for(int i=0;i<n;i++) cin>>p[i],p[i]--; int cnt=0; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(p[i]<=p[j]){ vis[i]|=(1<<j); } cnt+=(p[j]>p[i]); } } // if(cnt==0){ // int sum=1; // for(int i=1;i<=n;i++){ // sum=sum*i%mod; // } // cout<<sum<<"\n"; // return ; // } vector<int> dp((1<<n)); dp[0]=1; for(int i=1;i<(1<<n);i++){ int sum=0; for(int j=0;j<n;j++){ if((i>>j&1)&&(i&vis[j])==vis[j]){ add(sum,dp[i^(1<<j)]); } } dp[i]=sum; } if(cnt)cout<<2ll*dp[(1<<n)-1]%mod<<"\n"; else cout<<dp[(1<<n)-1]<<"\n"; } signed main() { //freopen("in.txt","r",stdin); int t=1; while(t--){ solve(); } }

2.特殊的图形

2.1 树（使用数学公式）

例题（F-Permutation of RBS_牛客小白月赛138）

#include <bits/stdc++.h> using namespace std; const int N = 500010,mod=1e9+7; typedef long long ll; int sz[N]; vector<int> v[N]; ll qmi(ll a,ll b) { ll res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void dfs(int u) { for(auto j:v[u]){ dfs(j); sz[u]+=sz[j]; } } void solve() { string s; int n; cin>>n; for(int i=0;i<=n;i++){ sz[i]=1; v[i].clear(); } cin >> s; stack<int> st; int cnt = 0; for (char c : s) { if (c == '(') { cnt++; if (st.empty()) { v[0].push_back(cnt); } else { int t=st.top(); v[t].push_back(cnt); } st.push(cnt); } else { st.pop(); } } dfs(0); ll ans=1; for(int i=1;i<=n;i++) ans=ans*i%mod; for(int i=1;i<=n;i++){ ans=ans*qmi(sz[i],mod-2)%mod; } cout<<ans<<"\n"; } int main() { int t=1; cin>>t; while(t--){ solve(); } }