ZigZagK的博客
[裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解
2018年5月23日 16:50
LOJ
查看标签

题目概述

给你 $n$ 种物品,每种物品有无数个,体积为 $V_i$ ,选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ,问方案数。

解题报告

怎么我一道HAOI题都不会啊,我实在太菜了(HAOI题太假了)

写成柿子就是验证是否存在 $\{a_{k+1}\}$ 使得 $\sum_{i=1}^{k}a_iV_i\equiv w(mod\ p)\Leftrightarrow \sum_{i=1}^{k}a_iV_i-a_{n+1}p=w$ ,如果 $k=2$ 的话那么就是裴蜀定理,实际上裴蜀定理可以推广到 $k$ 元线性同余方程,就是验证 $(V_1,V_2,\cdots,V_k,p)|w$ ,yy一下还是很显然的(不就是不会证吗,直接说不就好了)。然后我就不会做了QAQ,看题解……


再变形一下就是 $((V_1,p),(V_2,p),\cdots,(V_k,p))|(w,p)$ 。为什么这样变形?因为你会发现这么变形之后所有元素就限制在了 $p$ 的因子内!然后你就可以瞎搞了:定义 $f_{i,j}$ 表示用前 $i$ 个因子 $gcd$ 出第 $j$ 个因子的方案数,对于每个因子转移一下,最后 $O(1)$ 回答。

$10^9$ 之内因子个数是 $O(10^3)$ 的,颠覆了我的世界观……看来下次看到这种题要多往因子方面想……

示例程序

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int maxd=10000,maxn=1000000,MOD=1e9+7;

int n,te,P,D[maxd+5],num[maxd+5],f[2][maxd+5];
int pw[maxn+5];unordered_map<int,int> ID;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void Make(int x){
    for (int i=1,S=sqrt(x);i<=S;i++)
        if (!(x%i)) {D[++D[0]]=i;if (i<x/i) D[++D[0]]=x/i;}
    sort(D+1,D+1+D[0]);for (int i=1;i<=D[0];i++) ID[D[i]]=i;
}
int gcd(int a,int b) {if (!b) return a;return gcd(b,a%b);}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);readi(te);readi(P);Make(P);
    for (int i=1,x;i<=n;i++) readi(x),num[ID[gcd(x,P)]]++;
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=((LL)pw[i-1]<<1)%MOD;
    for (int i=1,c=1;i<=D[0];i++,c^=1){
        for (int j=1;j<=D[0];j++) f[c][j]=f[c^1][j];AMOD(f[c][i],pw[num[i]]-1);
        for (int j=1;j<=D[0];j++) AMOD(f[c][ID[gcd(D[i],D[j])]],(LL)f[c^1][j]*(pw[num[i]]-1)%MOD);
    }
    for (int i=D[0];i>1;i--)
        for (int j=i-1;j;j--)
            if (!(D[i]%D[j])) AMOD(f[D[0]&1][i],f[D[0]&1][j]);
    for (int i=1,x;i<=te;i++) readi(x),x=gcd(x,P),printf("%d\n",f[D[0]&1][ID[x]]);
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!