题解 P4444 [COCI2017-2018#3] Sažetak

· · 题解

update：修改了一些 LaTeX 问题（\not\mid->\nmid），增加了 k 的数据范围。

题目传送门

前置知识：

扩展欧几里得算法，容斥 / 子集反演。

题意：

分析：

记 s 表示 x 的前缀和，即 s_i=\sum_{j=1}^ix_j。

则条件即为已知 s_k-s_0,\,s_{2k}-s_k,\,\dots,\,s_n-s_{tk}。又已知 s_0=0，故条件转化为已知 s_k,s_{2k},\dots,s_n，即已知若干个前缀和。所以，x_i 被唯一确定，当且仅当 s_i 与 s_{i-1} 均已知。

考虑哪些 i 满足 s_i 已知。由上述分析知 s_i 已知当且仅当 \exists k_j,k_j\mid i 或 i=n。为了方便，我们令 k_{m+1}=n。这样，s_i 被确定当且仅当 \exists k_j,k_j\mid i。

考虑哪些 i 满足 x_i 被确定，即 s_{i-1} 与 s_i 均已知。x_i 被确定当且仅当 \exists k_{j_1},k_{j_1}\mid i 且 \exists k_{j_2},k_{j_2}\mid i-1。

若只有一对 k_{j_1},k_{j_2}，则可以令 i=ak_{j_1}=bk_{j_2}+1，有 ak_{j_1}-bk_{j_2}=1。由扩展欧几里得相关知识可以求解。

然而，此时有很多对 k，只需满足其中之一即可，故不能直接推出形如 i=ak 或 i=bk+1 的性质；若对所有 k 两两之间计算贡献，又会算重。注意到 m 非常小，所以可以对于所有 k_j 枚举是否有 k_j\mid i 或 k_j\mid i-1，避免了算重。具体地，对于全集 U=\{1,2,\dots,m+1\} 的子集 S,V，记 f(S,V) 为满足 j\in S\Leftrightarrow k_j\mid i，j\in V\Leftrightarrow k_j\mid i-1 的 i 的数量，我们可以考虑算出 \sum_{S\ne\varnothing,V\ne\varnothing}f(S,V)。

然而，f(S,V) 并不好算，因为即使我们知道了所有 k_j\mid i 是否成立，也与我们能求的“只有一对 k_{j_1},k_{j_2}”的情况相去甚远。但注意到如果忽略所有 k_j\nmid i 的限制，即只考虑 k_j\mid i，那么 i 受到的限制即为 \text{lcm}_{j\in S}\{k_j\}\mid i。记 K=\text{lcm}_{j\in S}\{k_j\}，情况转化为只有单个 K\mid i 的情况，是可做的。故考虑容斥。

具体地，记 h(S,V) 为满足 j\in S\Rightarrow k_j\mid i，j\in V\Rightarrow k_j\mid i-1 的 i 的数量（注意 \Rightarrow 与 \Leftrightarrow 的区别）。为了辅助，再记 g(S,V) 为满足 j\in S\Leftrightarrow k_j\mid i，j\in V\Rightarrow k_j\mid i-1 的 i 的数量。有：

\begin{aligned} g(S,V)=&\sum_{V_1\supseteq V}f(S,V_1)\\ \Rightarrow f(S,V)=&\sum_{V_1\supseteq V}(-1)^{|V|-|V_1|}g(S,V_1)\\ \Rightarrow \sum_{V\ne\varnothing}f(S,V)=&g(S,\varnothing)-f(S,\varnothing)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}g(S,V) \end{aligned}

同理，

\begin{aligned} h(S,V)=&\sum_{S_1\supseteq S}g(S_1,V)\\ \Rightarrow g(S,V)=&\sum_{S_1\supseteq S}(-1)^{|S|-|S_1|}h(S_1,V)\\ \Rightarrow \sum_{S\ne\varnothing}g(S,V)=&h(\varnothing,V)-g(\varnothing,V)\\ =&\sum_{S\ne\varnothing}(-1)^{|S|-1}h(S,V) \end{aligned}

故：

\begin{aligned} &\sum_{S\ne\varnothing}\sum_{V\ne\varnothing}f(S,V)\\ =&\sum_{S\ne\varnothing}\sum_{V\ne\varnothing}(-1)^{|V|-1}g(S,V)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}\sum_{S\ne\varnothing}g(S,V)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}\sum_{S\ne\varnothing}(-1)^{|S|-1}h(S,V)\\ =&\sum_{S\ne\varnothing,V\ne\varnothing}(-1)^{|S|+|V|}h(S,V) \end{aligned}

可以枚举 S,V，再用扩展欧几里得算法求出 h(S,V)，复杂度 2^{2m}\log n。

注意到存在 j_0 满足 j_0\in S\land j_0\in V 时，会推出 k_{j_0}\mid i\land k_{j_0}\mid i-1，得 k_{j_0}\mid 1，故一定无解，所以可以只枚举与 S 不交的 V，复杂度 3^m\log n。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;

const int mM=11+2, mS=1<<11|9;
ll exgcd(ll &a, ll &b, ll x, ll y) {
    if(!y) return a=1, b=0, x;
    ll res=exgcd(b, a, y, x%y);
    b-=x/y*a;
    return res;
}

int n, m, k[mM];
int lcm[mS], cnt[mS];
//lcm[s] 表示集合内所有 kj 的 lcm 

int main() {

    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        scanf("%d", k+i);
    }
    sort(k+1, k+m+1), m=unique(k+1, k+m+1)-k-1;
    k[++m]=n;

    rep(i, 1, m) {
        lcm[1<<i-1]=k[i];
    }
    lcm[0]=1;
    rep(s, 1, (1<<m)-1) {
        cnt[s]=cnt[s>>1]+(s&1);
        const int a=lcm[s&s-1], b=lcm[s&-s], g=__gcd(a, b);
        if(a>n || b>n || (ll) a/g*b>n) lcm[s]=n+1;
        //如果 lcm 过大，一定无解 
        else lcm[s]=a/g*b;
    }
    int ans=0;
    rep(s0, 1, (1<<m)-1) if(lcm[s0]<=n) {
        const ll x=lcm[s0]; //i mod x = 0
        for(int _1=_^s0, s1=_1; s1; s1=_1&s1-1) if(lcm[s1]<n) {
            const ll y=lcm[s1]; //i mod y = 1
            ll a, b, g=exgcd(a, b, x, y), l=x/g*y;
            if(g>1) continue;
            a=(a%y+y)%y;
            assert(a*x%y==1);
            ans+=(cnt[s0]+cnt[s1]&1? -1: 1)*(n/l+(n%l>=a*x));
        }
    }
    printf("%d\n", ans);
    return 0;
}