[WC2018] 州区划分 https://www.luogu.org/problemnew/show/P4221
注意审题:
1. 有序选择
2. 若干个州
3. 贡献是州满意度的乘积
枚举最后一个州是哪一个, 合法时候贡献 sum[s]^p, 否则贡献 0
存在欧拉回路: 每个点都是偶度数, 且图连通 (dfs 验证)
然后愉快子集卷积即可.
PS:
FMT 辣鸡,
FWT 可以节省一倍的常数! 这样才能通过此题
- #include<bits/stdc++.h>
- #define reg register int
- #define il inline
- #define fi first
- #define se second
- #define mk(a,b) make_pair(a,b)
- #define numb (ch^'0')
- using namespace std;
- typedef long long ll;
- template<class T>il void rd(T &x){
- char ch;x=0;bool fl=false;
- while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
- for(x=numb;isdigit(ch=getchar());x=x*10+numb);
- (fl==true)&&(x=-x);
- }
- template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
- template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
- template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
- namespace Miracle{
- const int N=24;
- const int mod=998244353;
- int n,m,p;
- int qm(int x,int y){
- int ret=1;
- while(y){
- if(y&1) ret=(ll)ret*x%mod;
- x=(ll)x*x%mod;
- y>>=1;
- }
- return ret;
- }
- int ad(int x,int y){
- return x+y>=mod?x+y-mod:x+y;
- }
- int f[N][1<<21];
- int g[N][1<<21];
- int w[N],sum[1<<21];
- int sz[1<<21];
- int to[N];
- void FWT(int *f,int n){
- for(reg p=2;p<=n;p<<=1){
- for(reg l=0;l<n;l+=p){
- for(reg k=l;k<l+p/2;++k){
- f[k+p/2]=ad(f[k],f[k+p/2]);
- }
- }
- }
- }
- void IFWT(int *f,int n){
- for(reg p=2;p<=n;p<<=1){
- for(reg l=0;l<n;l+=p){
- for(reg k=l;k<l+p/2;++k){
- f[k+p/2]=ad(f[k+p/2],mod-f[k]);
- }
- }
- }
- }
- int val(int v){
- // cout<<"bv"<<v<<endl;
- return p==0?1:(p==1?v:(ll)v*v%mod);
- }
- int tot;
- int vis[N];
- int inv[23333];
- void dfs(int x,int s){
- // cout<<"x"<<x<<"s"<<s<<endl;
- vis[x]=1;
- ++tot;
- for(reg i=0;i<n;++i){
- if((!vis[i])&&(s&(1<<i))&&(to[x]&(1<<i))){
- dfs(i,s);
- }
- }
- }
- int main(){
- rd(n);rd(m);rd(p);
- int x,y;
- inv[1]=1;
- for(reg i=2;i<=2500;++i){
- inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
- }
- for(reg i=1;i<=m;++i){
- rd(x);rd(y);--x;--y;
- to[x]|=(1<<y);to[y]|=(1<<x);
- }
- for(reg i=0;i<n;++i){
- rd(w[i]);
- }
- for(reg i=0;i<(1<<n);++i){
- sz[i]=sz[i>>1]+(i&1);
- for(reg j=0;j<n;++j){
- if(i&(1<<j)) sum[i]+=w[j];
- }
- }
- // cout<<"pre 1"<<endl;
- for(reg s=1;s<(1<<n);++s){
- int ji=0;
- tot=0;
- memset(vis,0,sizeof vis);
- dfs((__builtin_ctz(s&(-s))),s);
- // cout<<"s"<<s<<""<<__builtin_ctz(s&(-s))<<" tot "<<tot<<endl;
- // cout<<"tot"<<tot<<"sz"<<sz[s]<<endl;
- if(tot!=sz[s]) ji=233;
- for(reg i=0;i<n;++i){
- if(s&(1<<i)){
- ji+=(sz[to[i]&s]&1);
- }
- }
- // cout<<"ss"<<s<<"ji"<<ji<<endl;
- if(ji>0){
- // cout<<"val"<<val(sum[s])<<endl;
- g[sz[s]][s]=val(sum[s]);
- }
- }
- for(reg i=0;i<(1<<n);++i){
- f[0][i]=1;
- }
- // return 0;
- // cout<<"built"<<endl;
- for(reg i=1;i<=n;++i){
- FWT(g[i],(1<<n));
- // prt(g[i],0,(1<<n)-1);
- for(reg j=1;j<=i;++j){
- for(reg s=0;s<(1<<n);++s){
- f[i][s]=ad(f[i][s],(ll)g[j][s]*f[i-j][s]%mod);
- }
- }
- IFWT(f[i],(1<<n));
- // prt(f[i],0,(1<<n)-1);
- for(reg s=0;s<(1<<n);++s){
- // if(sz[s]==i)
- f[i][s]=(ll)val(inv[sum[s]])*f[i][s]%mod;
- // else f[i][s]=0;
- }
- if(i!=n) FWT(f[i],(1<<n));
- }
- printf("%d",f[n][(1<<n)-1]);
- return 0;
- }
- }
- signed main(){
- Miracle::main();
- return 0;
- }
- /*
- Author: *Miracle*
- Date: 2019/4/13 19:58:12
- */
- View Code
[WC2018] 州区划分
来源: http://www.bubuko.com/infodetail-3027247.html