堆/密文/树
堆
二叉堆是一種特殊的堆，其同時滿足完全二叉樹和堆的性質。完全二叉樹：令堆中節點數為?，我們將所有節點編號為\([1,n]\)，那么\(1\)號節點為根，其他所有節點滿足?號節點的父親為\(\lfloor\frac{i}{2} \rfloor\)號節點，
其中\(\lfloor\frac{i}{2} \rfloor\)表示\(\frac{i}{2}\)向下取整后的結果。
堆：每個節點的權值均不小于其父親節點的權值。
求有多少種不同的?個節點的二叉堆滿足所有節點權值均在\(1\)到\(?\)之間且互不相同，答案對\(10^9 + 7\)取模。
\(n\leq 10^9\)
【樣例輸入】
3
【樣例輸出】
2
容易得到\(DP\)方程：
\[ f_n=f_l\cdot f_r \cdot \binom{n-1}{l} \]
仔細觀察會發現一個二叉樹的兩顆子樹中至少有一個是滿二叉樹，所以我們可以預處理滿二叉樹的答案。
然后組合數部分可以用分塊打表的方法預處理階乘。
代碼（沒有表的）：
#include<bits/stdc++.h> #define ll long long #define N 2000005using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=1e9+7; ll ksm(ll t,ll x) {ll ans=1;for(;x;x>>=1,t=t*t%mod)if(x&1) ans=ans*t%mod;return ans; } int n;ll c[100]; const int blk=5e5; ll Fac[233]; ll Get_fac(int n) {int x=n/blk;ll ans=Fac[x];for(ll i=x*blk+1;i<=n;i++) ans=ans*i%mod;return ans; } ll Get_C(int n,int m) {return Get_fac(n)*ksm(Get_fac(m),mod-2)%mod*ksm(Get_fac(n-m),mod-2)%mod;}void Get_biao() {c[0]=1;c[1]=2;c[2]=20;c[3]=3432;c[4]=155117520;c[5]=997262645;c[6]=899707189;c[7]=876105808;c[8]=746311539;c[9]=856578165;c[10]=8323437;c[11]=749503558;c[12]=816339384;c[13]=429438005;c[14]=231982441;c[15]=650359664;c[16]=626569458;c[17]=693597544;c[18]=476836356;c[19]=807305820;c[20]=941911189;c[21]=426807449;c[22]=900586569;c[23]=481824850;c[24]=871608524;c[25]=88038971;c[26]=135219718;c[27]=915259147;c[28]=930678596;c[29]=0; } ll size[35]; ll pre[35]; map<int,int>id; ll dfs(int n) {if(n==1||n==0) return 1;if(id.find(n)!=id.end()) return pre[id[n]];int k=0;for(;size[k]*2<=n-1;k++);k--;int res=n-1-2*size[k];if(res>size[k]) {res-=size[k]+1;return dfs(size[k]<<1|1)*dfs(size[k]+res)%mod*Get_C(n-1,size[k]+res)%mod;} else {return dfs(size[k]+res)*dfs(size[k])%mod*Get_C(n-1,size[k])%mod;} }void solve() {Get_biao();int d=1;while((1ll<<d+1)-1<=n) d++;size[1]=1;for(int i=2;i<=d;i++) {size[i]=size[i-1]<<1|1;}for(int i=1;i<=d;i++) id[size[i]]=i;pre[0]=1;for(int i=1;i<=d;i++) {pre[i]=pre[i-1]*pre[i-1]%mod*Get_C(size[i-1]<<1,size[i-1])%mod;}cout<<dfs(n)<<"\n"; }int main() {n=Get();solve();return 0; }密文
【問題描述】
有一串長度為\(?\)的密文，密文的每一位都可以用一個非負整數來描述，并且每一位都有一個權值\(?_?\)。你可以進行任意多次操作，每次操作可以選擇連續一段密文，花費選擇的所有位上權值的異或和的代價獲得這段密文每一位的異或和。求至少需要花費多少代價才能將密文的每一位都破解出來。
【輸入格式】
第一行一個正整數\(?\)。
第二行\(?\)個非負整數，表示\(?_?\)。
【樣例輸入】
2
1 3
【樣例輸出】
3
\(n\leq 10^5 ,a_i\leq 10^9\)
和\(noip\)之前做過的一道題套路完全一樣，選擇一段區間\([l,r]\)就是得到了前綴異或和\(pre_r\)與\(pre_{l-1}\)的關系，我們要得到所有的\(pre_i\)與\(pre_0\)的關系。最小生成樹。
異或最小生成樹就是從高位到低位，將該位上不同的數分為兩個集合，集合之間最多只能有一條邊。
代碼：
#include<bits/stdc++.h> #define ll long long #define N 100005using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n; int a[N]; ll sum[N]; int st[N]; struct trie {int sn[2]; }tr[N*35]; int cnt=1;void Init() {for(int i=1;i<=cnt;i++) tr[i].sn[0]=tr[i].sn[1]=0;cnt=1; } void Insert(int t) {int v=1;for(int i=29;i>=0;i--) {int j=t>>i&1;if(!tr[v].sn[j]) tr[v].sn[j]=++cnt;v=tr[v].sn[j];} } int query(int t) {int v=1,ans=0;for(int i=29;i>=0;i--) {int j=t>>i&1;if(tr[v].sn[j]) v=tr[v].sn[j];else {ans+=1<<i,v=tr[v].sn[j^1];}}return ans; }vector<int>L,R; ll solve(int l,int r,int dep) {if(l>r) return 0;if(dep<0) return 0;L.clear(),R.clear();for(int i=l;i<=r;i++) {if(st[i]>>dep&1) R.push_back(st[i]);else L.push_back(st[i]);}int x=L.size();for(int i=0;i<x;i++) st[l+i]=L[i];for(int i=0;i<R.size();i++) st[l+x+i]=R[i];ll ans=0;if(L.size()&&R.size()) {Init();for(int i=0;i<L.size();i++) Insert(L[i]);int minn=1e9+7;for(int i=0;i<R.size();i++) minn=min(minn,query(R[i]));ans=minn;}ans+=solve(l,l+x-1,dep-1)+solve(l+x,r,dep-1);return ans; }int main() {n=Get();for(int i=1;i<=n;i++) a[i]=Get();for(int i=1;i<=n;i++) sum[i]=sum[i-1]^a[i];for(int i=0;i<=n;i++) st[i]=sum[i];cout<<solve(0,n,29);return 0; }樹
【問題描述】
給出一棵?個節點的樹?以及一棵?個節點的樹?，求?有多少個不同的連通子圖與?同構，答案對\(10^9 + 7\)取模。我們定義兩個圖同構當且僅當存在一個節點的對應方案使得每個圖中的每個節點恰好與另一個圖中的某個節點相對應，且如果在一個圖中兩個節點之間有連邊，它們在另一個圖中對應的兩個節點之間也有連邊。
【樣例輸入】
4
1 2
1 3
1 4
2
1 2
【樣例輸出】
3
\(n\leq 2000,m\leq 12\)
我們先給\(B\)樹定一個根。
設\(f_{i,j}\)表示\(A\)樹\(i\)節點與\(B\)樹\(j\)節點為根的樹同構的方案數。為了得到\(f_{i,j}\)，我們需要將\(i\)的子節點與\(j\)的子節點配對。當然，我們已經的到了\(f_{sn_i,sn_j}\)，我們就可以狀壓\(DP\)得到匹配上\(B\)的所有子節點的方案數。
樹hash用括號序比較穩。還要把加法變成異或。
如果\(j\)有幾個子節點是同構的，那么會算重\(\prod cnt_i!\)，\(cnt_i\)表示第\(i\)中子樹的個數。
復雜度\(O(nm^22^m)\)。一副很可過的樣子。
代碼：
#include<bits/stdc++.h> #define ll long long #define N 2005 #define M 15using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=1e9+7; const ll Mod=998244353;int n,m; ll f[N][M]; struct road {int to,next;}s[N<<1]; int h[N],cnt; void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;} vector<int>e[N]; ll fac[N],ifac[N]; ll ksm(ll t,ll x) {ll ans=1;for(;x;x>>=1,t=t*t%mod)if(x&1) ans=ans*t%mod;return ans; }ll Hash[N]; ll Hash2[N]; const ll p=666233,p2=134341; unsigned ll p3=233333;int size[N]; bool cmp(int a,int b) {if(size[a]!=size[b]) return size[a]<size[b];if(Hash[a]!=Hash[b]) return Hash[a]<Hash[b];return Hash2[a]<Hash2[b]; }ll t[N]; vector<int>sn[N]; int dep[N],mxdep[N]; void dfs1(int v,int fr) {size[v]=1;mxdep[v]=dep[v];for(int i=0;i<e[v].size();i++) {int to=e[v][i];if(to==fr) continue ;sn[v].push_back(to);dep[to]=dep[v]+1;dfs1(to,v);mxdep[v]=max(mxdep[v],mxdep[to]);size[v]+=size[to];}sort(sn[v].begin(),sn[v].end(),cmp);t[v]=1;for(int i=0;i<sn[v].size();i++) {int j=i;while(j+1<sn[v].size()&&size[sn[v][i]]==size[sn[v][j+1]]&&Hash[sn[v][i]]==Hash[sn[v][j+1]]&&Hash2[sn[v][j]]==Hash2[sn[v][j+1]]) j++;t[v]=t[v]*ifac[j-i+1]%mod;i=j;}Hash2[v]=Hash[v]='(';ll now=1,now2=1;for(int i=0;i<sn[v].size();i++) {Hash[v]=((Hash[v]*now%mod)^Hash[sn[v][i]])%mod;Hash2[v]=((Hash2[v]*now2%Mod)^Hash2[sn[v][i]])%Mod;now=now*p%mod;now2=now2*p2%Mod;}Hash[v]=(Hash[v]*p+')')%mod;Hash2[v]=(Hash2[v]*p+')')%Mod; }int st[N],top; int cal(int v,int u) {if(!top) return 0;static ll ans[1<<13],g[1<<13];int num=sn[u].size();for(int i=0;i<1<<num;i++) ans[i]=0;ans[0]=1;for(int i=1;i<=top;i++) {memcpy(g,ans,sizeof(g));int now=st[i];for(int j=0;j<num;j++) {if(!f[now][sn[u][j]]) continue ;int t=1<<j;for(int sta=0;sta<1<<num;sta++) {if(!(sta&t)) g[sta|t]=(g[sta|t]+ans[sta]*f[now][sn[u][j]])%mod;}}memcpy(ans,g,sizeof(g));}return ans[(1<<num)-1]*t[u]%mod; }ll ans; int rt; void solve(int v,int fr) {for(int i=1;i<=m;i++) if(sn[i].size()==0) f[v][i]=1;for(int i=h[v];i;i=s[i].next) {int to=s[i].to;if(to==fr) continue ;solve(to,v);}top=0;for(int i=h[v];i;i=s[i].next) {if(s[i].to==fr) continue ;st[++top]=s[i].to;}for(int i=1;i<=m;i++) {if(sn[i].size()) {f[v][i]=cal(v,i);}}(ans+=f[v][rt])%=mod; }#define pr pair<int,int> #define mp(a,b) make_pair(a,b) map<pr,int>vis; int work() {for(int i=1;i<=m;i++) sn[i].clear();for(int i=1;i<=m;i++) Hash[i]=Hash2[i]=0;dep[rt]=1;dfs1(rt,0);if(vis.find(mp(Hash[rt],Hash2[rt]))!=vis.end()) return 0;vis[mp(Hash[rt],Hash2[rt])]=1;memset(f,0,sizeof(f));ans=0;solve(1,0);return ans; }int main() {n=Get();int a,b;for(int i=1;i<n;i++) {a=Get(),b=Get();add(a,b),add(b,a);}m=Get();fac[0]=1;for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;ifac[m]=ksm(fac[m],mod-2);for(int i=m-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;for(int i=1;i<m;i++) {a=Get(),b=Get();e[a].push_back(b);e[b].push_back(a);}ll tot=0;for(rt=m;rt>=1;rt--) (tot+=work())%=mod;cout<<tot<<"\n";return 0; }轉載于:https://www.cnblogs.com/hchhch233/p/10495852.html
總結
- 上一篇： python @的用法
- 下一篇： 获取金蝶云试用许可