LuoguP5366 [SNOI2017]遺失的答案

題目描述

Solution

可以先簡化問題，特判$L$不是$G$倍數的情況。
然后令$n=?\frac{n}{G}?$,$L=?\frac{L}{G}?$。
現在相當于求出$1...n$中選擇若干數，使得$lcm$為$L$，$gcd$為$1$的方案數。

這就相當于將$L$質因數分解，令$L={\prod }_{i=1}^{cnt}{p}_i^{k_i}$，則顯然對于每一個$i$，都存在一個選擇的數$x$，使得$x$在$p_i$的指數為$k_i$，且都存在一個選擇的數$y$，使得$x$在$p_i$的指數為$0$。
除此之外，還需要保證每一個選擇的$x$的每一個質因數$p_i$的指數$\le k_i$。

我們先預處理出$L$的質因數分解和$n$以內可以選擇的數，用$S1$這一二進制串表示指數為$0$的條件是否達成，用$S2$這一二進制串表示指數為$k_i$的條件是否達成，記$S=S1S2$，求出$s[S]$表示有多少個可以選擇的狀態為$S$的數。

我們要求的方案，就是選擇若干個數，使得$S$的或和為全$1$。

這里要求強制選擇$x$，令$X$表示$x$對應的$01$狀態，那么我們就求一個前綴的或和為$S$的方案，再求一個后綴的答案，用$FWT$卷起來，再乘上$X$的狀態$S_X$可選的方案數即可。

這里的$01$狀態有$600$左右（大概就是一個質因子的指數為1的話會產生2倍的貢獻，若大于1就會產生3倍的貢獻，因此最壞也就這么大了）。時間復雜度$O(能過)......$。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int MAXN=1<<16; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } PR p[MAXN]; map<int,int> Map1,Map2; int f[705][MAXN],g[705][MAXN],ans[MAXN],Ans[MAXN]; int s[MAXN],a[MAXN],b[MAXN],id[MAXN],mi[MAXN],cnt,Cnt,n,G,L,num; int upd(int x,int y) { return x+y>=mods?x+y-mods:x+y; } void fwt(int *A,int n,int opt) {for (int i=1;i<n;i<<=1)for (int j=0;j<n;j+=(i<<1))for (int k=j;k<j+i;k++) A[k+i]=(opt==1?upd(A[k+i],A[k]):A[k+i]=upd(A[k+i],mods-A[k])); } void Divide(int x) {for (int i=2;i*i<=x;i++)if (x%i==0){p[++cnt]=MP(i,0);while (x%i==0) p[cnt].se++,x/=i;}if (x>1) p[++cnt]=MP(x,1); } void dfs(int x,int y,int t) {if (x==cnt+1) { if (t<=n) { if (!s[y]) a[++num]=y; s[y]++; Map1[t]=y; } return; }dfs(x+1,y+(1<<(x-1)),t);for (int i=1;i<p[x].se;i++) t*=p[x].fi,dfs(x+1,y,t);dfs(x+1,y+(1<<(cnt+x-1)),t*p[x].fi); } void Init() {f[0][0]=1;for (int i=0;i<num;i++)for (int j=0;j<1<<Cnt;j++) if (f[i][j])f[i+1][j]=upd(f[i+1][j],f[i][j]),f[i+1][j|a[i+1]]=upd(f[i+1][j|a[i+1]],1ll*f[i][j]*upd(mi[s[a[i+1]]],mods-1)%mods);g[num+1][0]=1;for (int i=num+1;i>=2;i--)for (int j=0;j<1<<Cnt;j++) if (g[i][j])g[i-1][j]=upd(g[i-1][j],g[i][j]),g[i-1][j|a[i-1]]=upd(g[i-1][j|a[i-1]],1ll*g[i][j]*upd(mi[s[a[i-1]]],mods-1)%mods); } void Merge() {for (int i=1;i<=num;i++){fwt(f[i-1],1<<Cnt,1),fwt(g[i+1],1<<Cnt,1);for (int j=0;j<1<<Cnt;j++) ans[j]=1ll*f[i-1][j]*g[i+1][j]%mods;fwt(ans,1<<Cnt,-1);for (int j=0;j<1<<Cnt;j++) if ((j|a[i])==((1<<Cnt)-1)) Ans[i]=upd(Ans[i],1ll*ans[j]*mi[s[a[i]]-1]%mods);} } int main() {int g,l;n=read(),g=read(),l=read(),n=n/g,L=l/g;if (l%g!=0) {int Case=read();while (Case--) { int x=read(); puts("0"); }return 0;}Divide(L),dfs(1,0,1),Cnt=cnt<<1,mi[0]=1;for (int i=1;i<1<<Cnt;i++) mi[i]=upd(mi[i-1],mi[i-1]);sort(a+1,a+num+1),Init(),Merge();for (int i=1;i<=num;i++) Map2[a[i]]=i;int Case=read();while (Case--){int x=read();if (x%g!=0) { puts("0"); continue; }x/=g;if (L%x!=0||x>n) puts("0");else printf("%d\n",Ans[Map2[Map1[x]]]);}return 0; }

似乎還有一種復雜度正確的方法。
大概是令$f_S$表示或和為$S$，且$X$必選的方案數，則有
$$[X\in S]2^{|S|?1}=\sum _{T?S}{f}_T$$
做一波清奇的反演，得到：
$$f_S=\sum _{T?S}[X\in T]2^{|T|?1}(?1{)}^{|S|?|T|}$$
然后直接容斥，時間復雜度為$O(q{2}^m)$，$m$表示$01$狀態的位數，由于總的不同$01$狀態共有$600$左右，因此判重之后時間復雜度很優秀。

總結

以上是生活随笔為你收集整理的LuoguP5366 [SNOI2017]遗失的答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。