我們剛剛知道那些題的解法-2
CF1292F
考慮對(duì)于 \(i,j\)，如果有 \(a_i|a_j\)，那么就從 \(i\) 向 \(j\) 連一條邊，考慮形成的弱連通分量之間互相獨(dú)立，因此可以用一個(gè)組合數(shù)乘起來，現(xiàn)在考慮一個(gè)連通分量。
設(shè) \(S\) 表示所有入度為 \(0\) 的點(diǎn)，\(T\) 為所有剩下的點(diǎn)組成的集合，那么顯然我們有一個(gè)刪除序列長(zhǎng)度的上界 \(|T|-1\)。其實(shí)，這個(gè)上界是可以達(dá)到的，證明只需要這樣考慮：現(xiàn)在考慮一個(gè)集合 \(M\) 中只有一個(gè)數(shù)，我們每次找到一個(gè) \(u,v\) 滿足 \(u\in S,v\in T\)，且 \(u\) 到 \(v,m\in M\) 有邊，然后把 \(v\) 加入 \(M\) 中。重復(fù)這個(gè)操作，顯然我們一定可以把所有數(shù)都加進(jìn)來。
現(xiàn)在我們就可以考慮一個(gè) DP，設(shè) \(f_{s,c}\) 表示我們現(xiàn)在的刪除序列里面有 \(c\) 個(gè)數(shù)，這 \(c\) 個(gè)數(shù)的所有因子組成的集合與 \(S\) 的交集為 \(s\)，方案數(shù)是多少，好像我們還需要記錄一個(gè)狀態(tài) \(t\) 表示哪些點(diǎn)加進(jìn)來了。但實(shí)際上有了 \(c\)，我們不需要記錄 \(t\)。考慮如果一個(gè)數(shù)加進(jìn)來可以使 \(s\) 變大，那么它顯然之前沒有加進(jìn)來過，否則，\(s\) 沒有變化，但是我們可以預(yù)處理一個(gè) \(cnt_s\) 表示因子集合為 \(s\) 的子集的數(shù)的個(gè)數(shù)，我們可以把滿足條件的數(shù)一起轉(zhuǎn)移。即 \(f_{s,c}\times cnt_s\to f_{s,c}\)。
我們現(xiàn)在有了一個(gè)復(fù)雜度是 \(O(2^{|S|}|T|^2)\) 的 DP。現(xiàn)在證明 \(|S|\le \frac{N}{4}\)，其中 \(N\) 是這個(gè)弱連通分量中最大的 \(a_i\)。
首先，所有大于 \(\frac{N}{2}\) 的 \(S\) 中的點(diǎn)一定是孤立點(diǎn)，因?yàn)樗鼈儾豢赡苓B到其它點(diǎn)，所以 \(S\) 中的元素只可能是 \(\le \frac{N}{2}\)。
其次，設(shè) \(f(x)\) 表示 \(x\) 不斷除以 \(2\) 之后得到的奇數(shù)，如果有 \(f_(a_i)=f_(a_j)\)，那么一定有 \(a_i\) 和 \(a_j\) 互為倍數(shù)關(guān)系。而 \(\frac{N}{2}\) 個(gè)數(shù)的 \(f(x)\) 的取值只有 \(\frac{N}{4}\) 種，所以 \(S\) 中的元素個(gè)數(shù)不會(huì)超過 \(\frac{N}{4}\)。
代碼：
int n,a[N],id[N],rd[N],ans,jie[N],invjie[N];
vi e[N],v,S,T;
int ts[N],cnt[M],f[M][N],sum;
bool vis[N];
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int a){return ksm(a,mod-2,mod);}
inline void dfs(int k){
vis[k]=1;v.pb(k);
for(int to:e[k])if(!vis[to]){
// printf("k=%d to=%d\n",k,to);
dfs(to);
}
}
inline int DP(){
for(int x:v){
// printf("x=%d ",x);
if(!id[x]) S.pb(a[x]);else T.pb(a[x]);
}
// puts("");
if(T.empty()){
S.clear();return -1;
}
rep(i,0,(int)T.size()-1){
int nows=0;
rep(j,0,(int)S.size()-1){
// printf("T[%d]=%d S[%d]=%d\n",i,T[i],j,S[j]);
if(T[i]%S[j]==0) nows|=(1<<j);
}
cnt[nows]++;ts[i]=nows;
// printf("ts[%d]=%d\n",i,nows);
}
rep(i,0,(int)S.size()-1){
rep(j,0,(1<<((int)S.size()))-1){
if((j>>i)&1) cnt[j]+=cnt[j^(1<<i)];
}
}
// printf("cnt[1]=%d\n",cnt[1]);
rep(i,0,(int)T.size()-1){
f[ts[i]][1]++;
}
rep(i,1,(int)T.size()-1)rep(j,0,(1<<((int)S.size()))-1)if(f[j][i]){
bool op=0;
rep(k,0,(int)T.size()-1){
if((ts[k]&j)==0) continue;
if((ts[k]&j)==ts[k]){
if(op) continue;
else{
// puts("");
f[j][i+1]=(f[j][i+1]+f[j][i]*(cnt[j]-i)%mod)%mod;op=1;
}
}
else f[j|ts[k]][i+1]=(f[j|ts[k]][i+1]+f[j][i])%mod;
}
}
int ans=f[(1<<((int)S.size()))-1][T.size()];
rep(i,0,(1<<((int)S.size()))-1)rep(j,1,T.size()) f[i][j]=0,cnt[i]=0,ts[j-1]=0;
sum+=T.size()-1;ans=ans*invjie[T.size()-1]%mod;
S.clear();T.clear();
return ans;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i]);
jie[0]=1;rep(i,1,n) jie[i]=1ll*jie[i-1]*i%mod;
invjie[n]=inv(jie[n]);dec(i,0,n-1) invjie[i]=invjie[i+1]*(i+1)%mod;
rep(i,1,n)rep(j,1,n){
if(i==j) continue;
if(a[j]%a[i]==0){
// printf("%d %d\n",i,j);
e[i].pb(j);id[j]++;rd[i]++;e[j].pb(i);
}
}
ans=1;sum=0;
// printf("ans=%d\n",ans);
rep(i,1,n)if(!vis[i]){
v.clear();dfs(i);
int nowans=DP();
if(nowans==-1) continue;
ans=ans*nowans%mod;
// printf("nowans=%d\n",nowans);
}
ans=ans*jie[sum]%mod;
printf("%d\n",ans);
return 0;
}
錯(cuò)誤總結(jié)：
- s,t 忘記清空。
- 組合數(shù)貢獻(xiàn)算錯(cuò)。
CF1290F
因?yàn)槭峭拱酝拱男螤顑H和每個(gè)向量的個(gè)數(shù)有關(guān)系，設(shè) \(c_i\) 表示第 \(i\) 個(gè)向量選的次數(shù)，那么我們可以轉(zhuǎn)化限制如下：
考慮 \(m\) 很大，但是 \(n\) 和 \(x_i\) 都很小，這個(gè)時(shí)候我們要考慮數(shù)位 DP，每當(dāng)出現(xiàn) \(\sum c_ia_i\le m\) 的時(shí)候一定要注意是不是數(shù)位 DP。
因?yàn)橛羞M(jìn)位，所以我們從小到大考慮填什么，在二進(jìn)制下考慮，因?yàn)檫@樣枚舉 \(n\) 個(gè)數(shù)某一位填什么的復(fù)雜度會(huì)小很多。設(shè) \(f_{i, px,py,nx,ny,0/1,0/1}\) 表示考慮了前 \(i\) 位，正數(shù) \(x\) 的進(jìn)位，正數(shù) \(y\) 的進(jìn)位，負(fù)數(shù) \(x\) 的進(jìn)位，負(fù)數(shù) \(y\) 的進(jìn)位，正數(shù) \(x\) 的前 \(i\) 位是否小于 \(m\)，正數(shù) \(y\) 的前 \(i\) 位是否小于 \(m\)。
int n,m,x[N],y[N],f[31][M][M][M][M][2][2];
inline int ge(int a,int b,int c){
if(a!=b) return (a<b)?0:1;return c;
}
inline int dfs(int p,int px,int py,int nx,int ny,int limx,int limy){
if(p==30) return (!px&&!py&&!nx&&!ny&&!limx&&!limy);
int &val=f[p][px][py][nx][ny][limx][limy];if(val!=-1) return val;
val=0;int dm=(m>>p)&1;
rep(i,0,(1<<n)-1){
int npx=px,npy=py,nnx=nx,nny=ny;
rep(j,0,n-1){
if((i>>j)&1){
(x[j]>0)?npx+=x[j]:nnx-=x[j];
(y[j]>0)?npy+=y[j]:nny-=y[j];
}
}
int dnpx=npx&1,dnpy=npy&1,dnnx=nnx&1,dnny=nny&1;
if(dnpx==dnnx&&dnpy==dnny){
val=(val+dfs(p+1,npx>>1,npy>>1,nnx>>1,nny>>1,ge(dnpx,dm,limx),ge(dnpy,dm,limy)))%mod;
}
}
return val;
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(m);rep(i,0,n-1) read(x[i]),read(y[i]);
mset(f,-1);
int ans=dfs(0,0,0,0,0,0,0)-1;
printf("%d\n",(ans+mod)%mod);
return 0;
}
數(shù)位 DP，如果不牽扯到進(jìn)位，那么從大往小 DP 易做限制，否則的話就從小往大做。
CF1286F
考慮所有操作 \(2\)，如果在所有被操作的數(shù)之間連邊，那么一定沒有環(huán)，否則還不如全用操作一，所以一定森林。現(xiàn)在我們要把整個(gè)集合分成若干個(gè)孤立點(diǎn)和盡可能多的森林，答案就是總個(gè)數(shù)減去樹的個(gè)數(shù)。
假設(shè)我們能判斷一個(gè)集合 \(s\) 是否能夠形成一顆樹，那么這個(gè)問題就解決了。設(shè) \(f_s\) 表示集合 \(s\) 中最多的樹的數(shù)量，枚舉子集轉(zhuǎn)移即可。
需要減枝，所以我們用自己更新別人。也就是說，我們枚舉一個(gè)集合 \(T\)，滿足 \(T\) 能形成一顆樹且 \(f_T=0\)，如果 \(T\) 不能分裂成更小的集合，那么首先枚舉到 \(T\) 其 DP 數(shù)組值一定為 \(0\)。然后枚舉所有包含它的集合。
至于孤立點(diǎn)，我們其實(shí)并沒有理睬他們，他們的 DP 數(shù)組永遠(yuǎn)是 \(0\)。
現(xiàn)在考慮 Check，我們可以把整棵樹黑白染色，染成二分圖，而左部點(diǎn)點(diǎn)權(quán)和與右部點(diǎn)點(diǎn)權(quán)和的差值的絕對(duì)值一定是小于等于樹的大小減 \(1\) 的，而且奇偶性和樹的大小減 \(1\) 相同，所以現(xiàn)在我們就考慮如何把一個(gè)集合分成兩個(gè)部分，一個(gè)想法是直接枚舉，不過復(fù)雜度太高。
采用折半搜索，搜索過程中把兩邊可能的集合差值從小到大排序，然后雙指針看是否有一對(duì)數(shù)滿足條件。
值得注意的是，如果集合中所有點(diǎn)的點(diǎn)權(quán)和小于等于樹的大小減 \(1\)，那么這種做法有可能把整棵樹劃分到一個(gè)集合上去，實(shí)現(xiàn)中，我們有一個(gè) \(nd\) 表示我們至少需要看到多少種這種答案，如果滿足上述條件，把 \(nd\) 從原來的 \(1\) 改成 \(3\) 即可。
可以證明，不管左部點(diǎn)和右部點(diǎn)的個(gè)數(shù)是多少，只要不為 \(0\)，都可以構(gòu)造出對(duì)應(yīng)的樹來。
int n,a[N],f[M],lg[M],b[N],bt,sum[M];
inline vi Get(int nl,int nr){
vi v;v.clear();
if(nl==nr){
if(b[nl]>0){v.pb(-b[nl]);v.pb(b[nl]);}
else{v.pb(b[nl]);v.pb(-b[nl]);}return v;
}
v=Get(nl+1,nr);
vi v1,v2;v1.clear();v2.clear();
rep(i,0,(int)v.size()-1) v1.pb(v[i]-b[nl]);
rep(i,0,(int)v.size()-1) v2.pb(v[i]+b[nl]);
vi now;now.clear();
int l=0,r=0;
while(l<(int)v1.size()&&r<(int)v2.size()){
if(v1[l]<v2[r]) now.pb(v1[l]),l++;
else now.pb(v2[r]),r++;
}
// printf("now.size()=%d l=%d r=%d\n",now.size(),l,r);
while(l<(int)v1.size()) now.pb(v1[l]),l++;
while(r<(int)v2.size()) now.pb(v2[r]),r++;
// printf("v1.size()=%d v2.size()=%d\n",v1.size(),v2.size());
// printf("now.size()=%d\n",now.size());
return now;
}
inline bool Check(int S){
if(__builtin_popcount(S)==1){
if(sum[S]==0) return 1;return 0;
}
int siz=__builtin_popcount(S)-1;
if((sum[S]-siz)&1) return 0;bt=0;
rep(i,0,n-1) if((S>>i)&1) b[++bt]=a[i+1];int mid=(1+bt)>>1;
vi L=Get(1,mid),R=Get(mid+1,bt);
// printf("mid=%d\n",mid);
int l=R.size(),r=R.size()-1;
// puts("L:");for(int x:L) printf("%d ",x);puts("");
// puts("R:");for(int x:R) printf("%d ",x);puts("");
int nd=1+(abs(sum[S])<=siz)*2;
// printf("nd=%d\n",nd);
for(int i=0;i<L.size();i++){
while(l&&L[i]+R[l-1]>=-siz) l--;
while(r>=0&&L[i]+R[r]>siz) r--;
// printf("l=%d r=%d\n",l,r);
nd-=min(nd,r-l+1);
// if(l<=r&&r!=R.size()) return 1;
// if(r==-1) return 0;
}
return (nd==0);
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);rep(i,1,n) read(a[i]),lg[1<<i]=i;
rep(i,1,n) sum[1<<(i-1)]+=a[i];
rep(i,0,n-1)rep(j,0,(1<<n)-1) if((j>>i)&1) sum[j]+=sum[j^(1<<i)];
lg[1]=0;
// printf("Check(7)=%d\n",Check(7));
for(int T=0;T<(1<<n);T++){
if(!f[T]&&Check(T)){
// puts("Now");
int t=T^((1<<n)-1);
for(int S=t;;S=(S-1)&t){
// printf("T|S=%d T=%d S=%d\n",T|S,T,S);
cmax(f[T|S],f[S]+1);
if(!S) break;
}
}
// printf("f[%d]=%d\n",T,f[T]);
}
printf("%lld\n",n-f[(1<<n)-1]);
return 0;
}
如果需要卡常，那么用自己更新別人加上減枝可能是一個(gè)很好的方法，因?yàn)槿绻D(zhuǎn)移 \(f_{to}\to f_{k}\) 中 \(f_{to}\) 不合法，那么用自己更新別人只需要判一次，但是用別人更新自己需要判 \(f_{to}\) 用到的次數(shù)次。
CFRound 819E
這個(gè)題沒做出來真的是比較失敗，感覺就差一點(diǎn)。
首先考慮環(huán)的種類，一共是有 \(3\) 中，分別為：\((i),(i,j),(i,j,i+1,j+1)\)，場(chǎng)上最后一種沒有想出來，考慮沒有其它的環(huán)，可以簡(jiǎn)單嘗試難以構(gòu)造出長(zhǎng)度為 \(3\) 和長(zhǎng)度大于 \(4\) 的合法的環(huán)。
考慮計(jì)算貢獻(xiàn)，不妨枚舉最后一種環(huán)的個(gè)數(shù)，設(shè)為 \(s\)，那么首先要從 \(n\) 個(gè)點(diǎn)里選出 \(2s\) 個(gè)互不相鄰的點(diǎn)，考慮每一個(gè)這樣的方案數(shù)都等價(jià)于我們從 \(n-2s\) 中選 \(2s\) 個(gè)點(diǎn)，然后在每個(gè)選出點(diǎn)后面加一個(gè)點(diǎn)。于是方案數(shù)就是 \(\binom{n-2s}{2s}\)，考慮接下來我們把選出的點(diǎn)任意排列，前一個(gè)與后一個(gè)配對(duì)，這樣每個(gè)方案數(shù)都被算重了 \(s!\) 次，所以總方案數(shù)為 \(\binom{n-2s}{2s}\frac{2s!}{s!}\)，剩下的點(diǎn)都是用第一種和第二種環(huán)，考慮設(shè) \(I_k\) 為 \(k\) 個(gè)點(diǎn)的方案數(shù)，顯然有：\(I_k=I_{k-1}+(k-1)I_{k-2}\)，所以最后總的方案數(shù)為：
int t,n,jie[N],invjie[N],I[N];
inline int ksm(int a,int b,int mod){
int res=1;while(b){if(b&1)res=1ll*a*res%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
inline int inv(int a){return ksm(a,mod-2,mod);}
inline int C(int n,int m){
if(n<m) return 0;return jie[n]*invjie[m]%mod*invjie[n-m]%mod;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
jie[0]=1;rep(i,1,Len) jie[i]=jie[i-1]*i%mod;
invjie[Len]=inv(jie[Len]);dec(i,0,Len-1) invjie[i]=invjie[i+1]*(i+1)%mod;
I[1]=1;I[0]=1;rep(i,2,Len) I[i]=(I[i-1]+(i-1)*I[i-2]%mod)%mod;
while(t--){
read(n);
int ans=0;
rep(i,0,n/4){
int nowans=C(n-2*i,2*i)*jie[2*i]%mod*invjie[i]%mod;
ans=(ans+nowans*I[n-i*4]%mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
P3911
令 \(cnt_i\) 表示 \(i\) 出現(xiàn)的次數(shù)，于是這個(gè)題就變得經(jīng)典了。
HDU5328
有：\(F(n)=F(n-1)+2n-1+G(n-1)\)，我們考慮計(jì)算 \(G(n)\)。
考慮第二個(gè)限制條件等價(jià)于 \(ij=\frac{n}w0obha2h00-1\)，而我們枚舉的 \(i,j\) 的上界都是嚴(yán)格大于這個(gè)值的，所以等價(jià)于枚舉所有的 \(i,j\)。因此，設(shè) \(H(n)=\sum_{i|n}[\gcd(i,\frac{n}{i})=1]\)，則原式相當(dāng)于：
其中，\(H(n)\) 相當(dāng)于 \(2\) 的 \(n\) 質(zhì)因子個(gè)數(shù)次冪，這是因?yàn)橄胍ベ|(zhì)，\(i\) 如果選擇了一種質(zhì)數(shù)，就必須拿完。而 \(G\) 可以調(diào)和級(jí)數(shù)的計(jì)算。
CF1279F
考慮設(shè) DP \(f_{i,j}\) 表示前 \(j\) 個(gè)數(shù)放了 \(i\) 個(gè)區(qū)間，其中最后一個(gè)區(qū)間的結(jié)尾為 \(j\)，\(1\) 或 \(0\) 的個(gè)數(shù)最多是多少，考慮 \(f_{i,j}\) 關(guān)于設(shè) \(f(k)\) 表示放了 \(k\) 個(gè)區(qū)間得到的結(jié)果，那么 \(f(k)\) 是一個(gè)凸函數(shù)，我們利用 \(wqs\) 二分可以優(yōu)化這道題。
int n,K,l,a[N],cnt[N][2],f[N],g[N],Ans,maxx,maxxid;
string s;
//最大化 id
inline bool DP(int id,int mid){
// printf("id=%d mid=%d\n",id,mid);
rep(i,1,n) f[i]=0,g[i]=0;
maxx=-INF;
rep(i,0,l-1) f[i]=cnt[i][id];
cmax(maxx,f[0]-cnt[0][id^1]);
maxxid=0;
rep(i,l,n){
f[i]=cnt[i-l][id]+maxx-mid+l;
g[i]=maxxid+1;
// cmax(maxx,f[i-l+1]-cnt[i-l+1][id^1]);
if(maxx<f[i-l+1]-cnt[i-l+1][id]){
maxx=f[i-l+1]-cnt[i-l+1][id];
maxxid=g[i-l+1];
}
}
// rep(i,0,n){
// printf("f[%d]=%d g[%d]=%d\n",i,f[i],i,g[i]);
// }
maxx=-INF;maxxid=-1;
rep(i,0,n){
if(maxx<f[i]+cnt[n][id]-cnt[i][id]){
maxx=f[i]+cnt[n][id]-cnt[i][id];maxxid=g[i];
}
}
// printf("maxx=%d maxxid=%d\n",maxx,maxxid);
return maxxid<=K;
}
inline void Solve(int id){
int L=0,R=n;
while(L<R){
int mid=(L+R)>>1;
if(DP(id,mid)) R=mid;else L=mid+1;
}
DP(id,L);cmax(Ans,maxx+L*K);
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(K);read(l);cin>>s;int lens=s.length()-1;
rep(i,0,lens) if(s[i]>='a'&&s[i]<='z') a[i+1]=0;else a[i+1]=1;
if(K*l>=n){
puts("0");return 0;
}
rep(i,1,n){
cnt[i][0]=cnt[i-1][0];cnt[i][1]=cnt[i-1][1];
cnt[i][a[i]]++;
}
Solve(0);
// printf("Ans=%d\n",Ans);
Solve(1);
// printf("Ans=%d\n",Ans);
printf("%lld\n",n-Ans);
return 0;
}
/*
+ 統(tǒng)計(jì)答案出錯(cuò)
+ 應(yīng)為 L*K 而非 L*maxxid
+ 預(yù)處理出錯(cuò)
+ 忘開 long long
*/
CF1276D
考慮刪點(diǎn)序列計(jì)數(shù)等價(jià)于刪點(diǎn)方案計(jì)數(shù)，兩個(gè)方法不同當(dāng)且僅當(dāng)存在至少一條邊選擇的點(diǎn)不同。因此可以考慮 DP。
一個(gè)點(diǎn)有 \(4\) 中狀態(tài)，分別為：沒有被刪，在遇到父親之前被刪，在遇到父親是被刪，在遇到父親之后被刪。直接 DP 轉(zhuǎn)移即可。
轉(zhuǎn)移舉一個(gè)例子，例如考慮 \(f_{k,1}\) 的轉(zhuǎn)移，首先枚舉 \(v\) 表示 \(k\) 是由通過 \(v\) 刪掉的，那么 \(v\) 一定沒有被刪，所以 \(v\) 的狀態(tài)為 \(0,3\)，前面點(diǎn)的狀態(tài)只可能是 \(1,2\)，后面點(diǎn)的狀態(tài)只可能是 \(0,1,3\)，所以需要預(yù)處理前綴和后綴積。
int n,f[N][4],pre[N],suf[N];
vc<P> e[N];
inline void dfs(int k,int fa){
for(P to:e[k])if(to.se!=fa){dfs(to.se,k);}
rep(i,0,(int)e[k].size()-1) pre[i]=suf[i]=0;
int id=-1;rep(i,0,(int)e[k].size()-1)if(e[k][i].se==fa){id=i;break;}
int faid=e[k][id].fi;
e[k].erase(e[k].begin()+id);
if(e[k].size()==0){
f[k][0]=1;f[k][2]=1;return;
}
rep(i,0,(int)e[k].size()-1){
if(i==0) pre[i]=(f[e[k][i].se][1]+f[e[k][i].se][2])%mod;
else pre[i]=1ll*pre[i-1]*((f[e[k][i].se][1]+f[e[k][i].se][2])%mod)%mod;
}
suf[e[k].size()]=1;
dec(i,0,(int)e[k].size()-1){
suf[i]=1ll*suf[i+1]*((f[e[k][i].se][0]+f[e[k][i].se][1]+f[e[k][i].se][3])%mod)%mod;
}
rep(i,0,(int)e[k].size()-1){
int nowans=1;
if(i!=0) nowans=nowans*pre[i-1]%mod;
if(i!=(int)e[k].size()-1) nowans=nowans*suf[i+1]%mod;
nowans=nowans*(f[e[k][i].se][0]+f[e[k][i].se][3])%mod;
if(e[k][i].fi<faid){
f[k][1]=(f[k][1]+nowans)%mod;
}
else{
f[k][3]=(f[k][3]+nowans)%mod;
}
}
f[k][0]=pre[(int)e[k].size()-1];
f[k][2]=1;
rep(i,0,(int)e[k].size()-1){
if(e[k][i].fi<faid){
f[k][2]=f[k][2]*(f[e[k][i].se][1]+f[e[k][i].se][2])%mod;
}
else{
f[k][2]=f[k][2]*(f[e[k][i].se][0]+f[e[k][i].se][1]+f[e[k][i].se][3])%mod;
}
}
// rep(i,0,3) printf("f[%d][%d]=%d\n",k,i,f[k][i]);
return;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);
rep(i,1,n-1){
int u,v;read(u);read(v);e[u].pb(mp(i,v));e[v].pb(mp(i,u));
}
e[1].pb(mp(0,0));
rep(i,1,n) sort(e[i].begin(),e[i].end());
dfs(1,0);
int ans=0;
ans=(f[1][0]+f[1][1]+f[1][3])%mod;
printf("%lld\n",ans);
return 0;
}
CF1225G
考慮如果能有一組答案，那么一定滿足能有一組 \(p_i\) 使得 \(\frac{a_i}{k^{p_i}}\) 全部加起來等于 \(1\)。這是相互等價(jià)的。
于是我們可以有一組 \(DP\)，設(shè) \(f_{S,x}\) 表示用集合 \(S\)，能不能把 \(x\) 表示出來，轉(zhuǎn)移有兩種，一種是加一個(gè)數(shù)，另一種是除以 \(k\)，注意著里加一個(gè) \(x\) 是需要枚舉最后一個(gè)加的是哪一個(gè)，因?yàn)榧尤爰系捻樞蚴切枰紤]的。可以用 bitset 進(jìn)行加速。
int n,k,a[N],sum,b[N];
bitset<2001> f[N];
priority_queue<P > q;
inline void ge(int s,int x){
if(!s) return;
if(x*k<=2000&&f[s][x*k]==1){
rep(i,0,n-1) if((s>>i)&1) b[i+1]++;
ge(s,x*k);return;
}
rep(i,1,n) if(((s>>(i-1))&1)&&x>=a[i]){
if(f[s^(1<<(i-1))][x-a[i]]){ge(s^(1<<(i-1)),x-a[i]);return;}
}
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(k);rep(i,1,n) read(a[i]);f[0][0]=1;
rep(i,1,n) sum+=a[i];
for(int i=0;i<(1<<n);i++){
rep(j,1,n) if((i>>(j-1))&1){
// puts("Here");
// cout<<f[i^(1<<(j-1))]<<endl;
// printf("a[j]=%d\n",a[j]);
f[i]|=(f[i^(1<<(j-1))]<<a[j]);
}
dec(j,1,sum/k){
// f[i][j]=f[i][j*k];
if(f[i][j*k]){
// printf("j=%d\n",j);
f[i][j]=1;
}
}
// printf("i=%d:\n",i);
// cout<<f[i]<<endl;
}
if(!f[(1<<n)-1][1]){puts("NO");return 0;}
else{
puts("YES");
ge((1<<n)-1,1);
// rep(i,1,n) printf("b[%d]=%d\n",i,b[i]);
rep(i,1,n) q.push({b[i],a[i]});
while(q.size()>1){
P n1=q.top();q.pop();
P n2=q.top();q.pop();
printf("%d %d\n",n1.se,n2.se);
n1.se+=n2.se;
while(n1.se%k==0){
n1.se/=k;n1.fi--;
}
q.push(n1);
}
}
return 0;
}
犯的錯(cuò)誤：
- DP 數(shù)組第二種轉(zhuǎn)移賦值出現(xiàn)錯(cuò)誤。
- 遞歸沒設(shè)置結(jié)束條件
浙公網(wǎng)安備 33010602011771號(hào)