题意:转化后变为:给一张 \(n\) 个点的图,你需要给每个点染上 \([1,k]\) 中的某个颜色,图上有 \(m\) 条边,每条边 \((u,v)\) 有两种边权 \(w_1\)(当 \(u,v\) 颜色相同时)和 \(w_2\)(当 \(u,v\) 颜色不同时),求所有染色方案的图中边权积之和。
题解:
考虑一种颜色一种颜色地加入,使用状压即可做到 \(O(k\cdot 3^n)\)。
这样就可以过了,结果考场上没想出来()大概是因为题目的边的给出方式太奇怪,导致我一直在推性质……
事实上有更优秀的 \(O(3^n)\) 的做法:仍然考虑状压,先不记录已经加入的颜色,考虑新加入一个颜色相同的点集时,给它在 \([1,k]\) 中随便赋一种颜色,但这可能会算重,容斥即可,可能需要手推一下容斥系数。
#include<bits/stdc++.h>
#define N 18
#define PN 150000
using namespace std;
namespace modular
{
const int mod=1000000007;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void Dec(int &x,int y){x=x-y<0?x-y+mod:x-y;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
}using namespace modular;
inline int poww(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
const int inv9=poww(9,mod-2);
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int nq,id[N<<1];
int n,q,ql[N],qr[N];
int nn,b[N<<1],fa[N<<1];
int coef[N<<1],upd[N<<1],trans[PN];
int f[11][PN];
bool vis[N];
int find(int x)
{
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int calc(int len)
{
return mul(inv9,dec(poww(10,len),1));
}
int main()
{
n=read(),q=read();
for(int i=1;i<=q;i++)
ql[i]=read(),qr[i]=read(),b[++nn]=ql[i]-1,b[++nn]=qr[i];
// b[++nn]=0;
sort(b+1,b+nn+1);
nn=unique(b+1,b+nn+1)-b-1;
// assert(b[1]==0);
for(int i=1;i<=nn;i++) fa[i]=i;
for(int i=1;i<=q;i++)
{
ql[i]=lower_bound(b+1,b+nn+1,ql[i]-1)-b;
qr[i]=lower_bound(b+1,b+nn+1,qr[i])-b;
int x=find(ql[i]),y=find(qr[i]);
if(x!=y) fa[x]=y;
}
for(int i=1;i<=nn;i++)
if(find(i)==i) id[i]=++nq;
int prod=1;
for(int i=1;i<nn;i++)
{
coef[i]=calc(b[i+1]-b[i]);
upd[i]=mul(coef[i]+1,poww(coef[i],mod-2));
Mul(prod,coef[i]);
}
int maxn=(1<<nq)-1;
for(int S=0;S<=maxn;S++)
{
for(int i=1;i<=nq;i++)
if((S>>(i-1))&1) vis[i]=1;
trans[S]=1;
for(int i=1;i<nn;i++)
if(vis[id[find(i)]]&&vis[id[find(i+1)]])
Mul(trans[S],upd[i]);
for(int i=1;i<=nq;i++)
if((S>>(i-1))&1) vis[i]=0;
}
f[0][0]=prod;
for(int i=1;i<10;i++)
{
for(int S=0;S<=maxn;S++)
{
for(int lS=S;;lS=(lS-1)&S)
{
int nS=S^lS;
Add(f[i][S],mul(trans[nS],f[i-1][lS]));
if(!lS) break;
}
}
}
int suf=mul(f[9][maxn],poww(10,n-b[nn]));
printf("%d\n",mul(poww(10,b[1]),mul(inv9,suf)));
return 0;
}
标签:ch,Multiple,int,状压,XSY3513,Nine,inline,颜色,mod
From: https://www.cnblogs.com/ez-lcw/p/16840986.html