bzoj 5019 [Snoi2017]遗失的答案

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=5019

题解

如果L不是G的倍数答案为0

下面考虑G|L的情况

将G,L质因数分解

设$L=p_1^{l_1} \times p_2^{l_2} \times ... \times p_t^{l_t}$

那么G的所有质因数肯定在$p_1 ~ p_t$之间所以我们可以把G也写成

$G=p_1^{g_1} \times p_2^{g_2} \times ... \times p_t^{g_t}$

那么我们选的数满足以下条件:

2. 我们把ai质因数分解

bi是一个数组记录了ai质因数分解后每一项的次数

那么我们有

根据条件1, 我们得出能够选的数不超过800个, 可以处理出来,放进数组a中

根据条件2, 我们可以状压dp

令dp[i][mask]表示当前考虑到第i个数,当前状态为mask的方案数

mask一共2*t位其中第2*i-1位表示当前选的数的集合能否满足$min(b_{j_i})=g_i$

第2*i为表示当前选的数的集合能否满足$max(b_{j_i})=l_i$

那么当mask全为1的时候就满足题意了

那么对于一个数x,包含x的满足题意的方案数=总数-不包含x的方案数

总数已经得到,就是dp[n][mxst]

不包含x的方案数如何求呢

令dp2[i][mask]表示倒着做当前第i个数,状态为mask的方案数

那么ans[i]=sum(dp[i-1][state]*dp[i+1][state2],state|state2=mxst)

这个做法复杂度O(800*mxst*mxst) 超时

我们要去掉一个mxst

如果我们能够处理出f[i][st]表示倒着考虑到第i个数,当前的状态包含了st的方案数

那么ans[i]=sum(dp[i-1][state]*f[i+1][mxst-state]) 就可以了

我们可以用一种奇妙的方法从dp2处理出f 具体见代码

Code

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll read(){

     ll x=,f=;char c=getchar();

     while(c<'' || c>''){if(c=='-')f=-;c=getchar();}

     while(c>='' && c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 const int mod=1e9+;

 int n,G,L,Q;

 int pr[],cnt,num[],mi[];

 int num2[],mi2[];

 int a[],tot,ok[];

 int dp1[][],dp2[][];

 map<int,int> ans;

 inline void pl(int &a,int b){

     a=a+b;if(a>mod) a-=mod;

 }

 int main(){

 #ifdef LZT

     freopen("in","r",stdin);

 #endif

     n=read();G=read();L=read();Q=read();

     if(L%G){

         while(Q--)

             puts("");

         return ;

     }

     int t=L;

     for(int i=;i<=t;i++){

         if(t%i) continue;

         pr[++cnt]=i,mi[cnt]=;

         while(t%i==) t=t/i,num[cnt]++,mi[cnt]*=i;

     }

     if(t!=){pr[++cnt]=t,num[cnt]=,mi[cnt]=t;}

     t=G;

     for(int i=;i<=cnt;i++){

         mi2[i]=;

         while(t%pr[i]==){

             t=t/pr[i];

             num2[i]++;

             mi2[i]*=pr[i];

         }

     }

     for(int i=;i*G<=L && i*G<=n;i++)

         if((L/G)%i==) a[++tot]=i*G;

     for(int i=;i<=tot;i++){

         int nw=a[i];

         for(int j=cnt;j>=;j--){

             ok[i]<<=;if(nw%mi[j]==) ok[i]|=;

             ok[i]<<=;if((nw/mi2[j])%pr[j]) ok[i]|=;

         }

     }

     int mxst=(<<(*cnt))-;

     for(int i=;i<=tot;i++){

         dp1[i-][]=;

         for(int st=;st<=mxst;st++){

             pl(dp1[i][st],dp1[i-][st]);

             if(dp1[i-][st]) pl(dp1[i][st|ok[i]],dp1[i-][st]);

         }

     }

     for(int i=tot;i>=;i--){

         dp2[i+][]=;

         for(int st=;st<=mxst;st++){

             pl(dp2[i][st],dp2[i+][st]);

             if(dp2[i+][st]) pl(dp2[i][st|ok[i]],dp2[i+][st]);

         }

     }

     ans[a[]]=(dp1[tot][mxst]-dp2[][mxst]+mod)%mod;

     ans[a[tot]]=(dp1[tot][mxst]-dp1[tot-][mxst]+mod)%mod;

     //处理f

     for(int i=;i<=tot;i++){

         for(int k=;k<(*cnt);k++){

             for(int st=;st<=mxst;st++){

                 if((st&(<<k))==)

                     pl(dp2[i][st],dp2[i][st|(<<k)]);

             }

         }

     }

     for(int i=;i<tot;i++){

         int nw=;

         for(int st=;st<=mxst;st++){

             int rem=((<<(*cnt))-)-st;

             pl(nw,dp1[i-][st]*1ll*dp2[i+][rem]%mod);

         }

         ans[a[i]]=(dp1[tot][mxst]-nw+mod)%mod;

     }

     while(Q--){

         int x=read();

         printf("%d\n",ans[x]);

     }

     return ;

 }

 /*

 5 1 30

 5

 1 2 3 4 5

 */

Review

动机?

分解质因数是显然的

然后对于这种满足最小公倍数等于什么或者最大公约数等于什么的题目我们应该自然地想到每一个质因数分开处理

然后对于这种满足最小公倍数等于什么并且最大公约数等于什么的题目我们应该自然地想到状压dp

至于那个处理部分就只能靠积累了

处理部分的正确性证明:

对于两个状态st1,st2 假设st1∈st2

假设st2中比st1多出来的分别在第a1,a2,...,ak位并且a1<a2<...<ak

那么会发生以下过程

f[st2-(1<<a1)]+=f[st2]

f[st2-(1<<a1)-(1<<a2)]+=f[st2-(1<<a1)]

...

f[st1]=f[st2-(1<<a1)-(1<<a2)-...-(1<<ak)]+=f[st2-(1<<a1)-(1<<a2)-...-(1<<a(k-1))]

这样st2的值被加进了st1中

所以这个过程是正确的

(UPD: 这个处理被称为Fast Zeta Transform 快速ζ变换)(真是有趣一天做到两道用到这个的题)

巴特西

bzoj 5019 [Snoi2017]遗失的答案

题面

题解

Code

Review

最新文章

热门文章