发布日期：2021-06-27 15:38:00 浏览次数：2 分类：技术文章

本文共 5650 字，大约阅读时间需要 18 分钟。

题面

有一个未知的序列 x，长度为 n。它的 K-划分序列 y 指的是每连续 K 个数的和得到划分序列，y[1]=x[1]+x[2]+....+x[K]，y[2]=x[K+1]+x[K+2]+....+x[K+K]....。若 n 不被 K 整除，则 y[n/K+1]可以由少于 K 个数加起来。比如 n=13，K=5，则 y[1]=x[1]+...+x[5]，y[2]=x[6]+....+x[10]，y[3]=x[11]+x[12]+ x[13]。若小 A 只确定 x 的 K[1]划分序列以及 K[2]划分序列....K[M]划分序列的值情况下，问她可以确定 x 多少个元素的值。

输入格式

第一行输入两个正整数 n，M。第二行输入 M 个正整数表示 K[1],K[2].....K[M]。

输出格式

输出 1 个整数，表示能确定的元素

Sample datas

sample input #1

3 12

sample output #1

sample input #2

6 22 3

sample output #2

sample input #3

123456789 35 6 9

sample output #3

10973937

sample input #4

4833827 47 8 9 10

sample output #4

【样例解释】

【样例 1 解释】

小 A 知道 x 的 2-划分序列，即分别知道 x[1]+x[2]，x[3]的值。

小 A 可以知道 x[3]的值。

【样例 2 解释】

小 A 知道 x 的 2-划分序列，即分别知道 x[1]+x[2]，x[3]+x[4]，x[5]+x[6] 的值。

小 A 知道 x 的 3-划分序列，即分别知道 x[1]+x[2]+x[3] ，x[4]+x[5]+x[6] 的值。

小 A 可以知道 x[3],x[4]的值，个数为 2.

【数据范围】

对于 20%的数据，3 ≤ 𝑁 ≤ 2000, 𝑀 ≤ 3。对于 40%的数据，3 ≤ 𝑁 ≤ 5 ∗ 10^6。对于 100%的数据，3 ≤ 𝑁 ≤ 10^9, 1 ≤ 𝑀 ≤ 10，2 ≤ 𝐾[𝑖] < 𝑁。

题解

（真毒瘤的错误）

实际上给你一个K-划分是告诉你了前 k 个(sum[k])、前 2k 个(sum[2k])、前 3k 个(sum[3k])……的前缀和sum分别是多少，

而且我们知道，在只知道前缀和数组sum的前提下，你要知道原本的第 i 个位置的数字，当且仅当知道了 sum[i] 和 sum[i-1] 然后相减所得，没有别的方法可以得到它，就算你知道其它所有的 sum[] 是多少，没那两个你也是算不出来的。

因此，渐渐就有思路了。

当你新得到一个 a[i] 时（即原题中的 K[i] ~~大写字母打着有些麻烦，就习惯地用 a[i] 了~~ ），你得计算 a[i] 贡献，

a[i] 的贡献就两种：

x 为 a[i] 的倍数，sum[x] 原本不知道，sum[x+1]原本知道，此时的 x+1 应加入贡献

x 为 a[i] 的倍数，sum[x] 原本不知道，sum[x -1]原本知道，此时的 x 应加入贡献

我们设上面两句话的 x 为 k*a[i]，则 k 分别要满足的条件为：

$\begin{Bmatrix} \exists j<i\;,\;k\cdot ai \equiv -1(\!\!\!\mod aj)\\ \forall j<i\;,\;k\cdot ai \not\equiv 0\;\;(\!\!\!\mod aj) \end{B}$ （初中的同学看过来：“ $\exists$ ” 是 “存在” 的意思，即存在一个小于 i 的 j，满足...，“ $\forall$ ” 是 “任意” 的意思，即对于任意的小于 i 的 j，满足...，大括号内两个条件要同时满足）

$\begin{Bmatrix} \exists j<i\;,\;k\cdot ai \equiv 1(\!\!\!\mod aj)\\ \forall j<i\;,\;k\cdot ai \not\equiv 0(\!\!\!\mod aj) \end{B}$

我们知道，对于每个 j < i ，如果分别求满足上述条件的 k 的数量，显然大概率会算重，而且并不是上面两个式子应有的解法，

但是，这样求又是最快的，怎么办呢，用容斥！

我们把大括号内两个条件分开，再把对于每个 j 的条件分开，一共得到 2 * (i-1) 个条件，然后枚举 $2^{2i-2}$ 种状态做容斥，下面那个 “ $\not\equiv$ ” 的式子，就可以把它变成 “ $\equiv$ ”的式子来算，这样更方便容斥。

对于只有一个条件的状态，我们很好算，但是对于很多条件的状态就显得困难，不急，我们继续推

上述两个大括号可以等价于：

$\begin{Bmatrix} \exists j<i\;,\;k \equiv -ai^{-1}(\!\!\!\mod aj)\\ !\;(\exists j<i\;,\;k \equiv 0(\!\!\!\mod aj/\gcd(ai,aj)) ) \end{B}$

$\begin{Bmatrix} \exists j<i\;,\;k \equiv ai^{-1}(\!\!\!\mod aj)\\ !\;(\exists j<i\;,\;k \equiv 0(\!\!\!\mod aj/\gcd(ai,aj)) ) \end{B}$

把一些条件单独拿出来就是这样的形式：

$\left\{\begin{matrix} k\equiv A_1\;\;(\!\!\!\mod B_1)\\ k\equiv A_2\;\;(\!\!\!\mod B_2)\\ \cdots \\ \end{matrix}\right.$

这是个线性同余方程组，我们可以用来做，

最后求得了一个方程：

$k \equiv A_{final}\;\;(\!\!\!\mod B_{final})$

k 的数量就可以直接做除法了！

把两个大括号分别求贡献，

由于我用记忆化处理每个状态，每次算一个状态就只用算一次式子合并，时间复杂度 $O(log\cdot2^{2m-2})$ （自己证一下吧）

CODE

记忆化直接递归，白爆60分，呜呼！

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 15#define LL long long#define DB double#define ENDL putchar('\n')#define lowbit(x) ((-x)&(x))#pragma GCC optimize(2)LL read() { LL f = 1,x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();} while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();} return f * x;}const int MOD = 1000000007;int n,m,i,j,s,o,k;LL a[MAXN];LL gcd(LL a,LL b) {return b==0 ? a:gcd(b,a%b);}LL exgcd(LL a,LL b,LL &x,LL &y) { if(b == 0) { x = 1;y = 0;return a; } LL r = exgcd(b,a%b,y,x); y -= x*(a/b); return r;}struct sz{ LL a,b; sz(){a=b=0;} sz(LL A,LL B){a=A;b=B;}}dp1[1<<10|5],dp2[1<<10|5];sz merg(sz x,sz y) { if(x.b == 0 || y.b == 0) return sz(); if(x.a > y.a) swap(x,y); if(x.b > n) { if(x.a % y.b == y.a) return x; else return sz(); } if(y.b > n) { if(y.a % x.b == x.a) return y; else return sz(); } LL k1,k2,re = y.a - x.a; LL gc = exgcd(x.b,y.b,k1,k2); LL lc = x.b / gc * y.b; if(re % gc) return sz(); k1 *= re / gc; sz as = sz((x.a + x.b*k1) % lc,lc); if(as.a<0) as.a+=as.b; if(as.a > n) return sz(); return as;}int f1[1<<10|5],f2[1<<10|5],ct[1<<10|5];sz DP1(int x) { if(f1[x]) return dp1[x]; f1[x] = 1; return (dp1[x] = merg(DP1(x-lowbit(x)),DP1(lowbit(x))));// 您可想过，这里曾是 return merg(DP1(x-lowbit(x)),DP1(lowbit(x))); ？}sz DP2(int x) { if(f2[x]) return dp2[x]; f2[x] = 1; return (dp2[x] = merg(DP2(x-lowbit(x)),DP2(lowbit(x))));}int ANS1(sz s,int ai) { int as = (((n-1)/ai) - s.a) / s.b + 1; if(s.a == 0) as --; return as;}int ANS2(sz s,int ai) { int as = ((n/ai) - s.a) / s.b + 1; if(s.a == 0) as --; return as;}int main() { n = read();m = read(); for(int i = 1;i < 1024;i ++) ct[i] = ct[i-lowbit(i)] + 1; int ans = 0; bool flag = 1,flag2 = 0; for(int i = 1;i <= m;i ++) { a[i] = read();// printf("a[%d]=%d : \n",i,a[i]); bool fl = 0; for(int j = 1;j < i;j ++) { if(a[i] % a[j] == 0) fl = 1; } if(fl) { i --;m --; continue; } memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); f1[0] = 1;dp1[0] = sz(0,1); int tp = (1<<(i-1))-1; for(int j = 1;j < i;j ++) {//k*ai ≡-1 (\mod aj) int gc; if((gc=gcd(a[i],a[j])) == 1) { LL x,y; exgcd(a[i],a[j],x,y); x = (a[j] - x % a[j]) % a[j]; dp2[1<<(j-1)] = sz(x,a[j]); } else dp2[1<<(j-1)] = sz(); f2[1<<(j-1)] = 1; dp1[1<<(j-1)] = sz(0,a[j]/gc); f1[1<<(j-1)] = 1;// printf("dp1[%d]=%d(%d) dp2[%d]=%d(%d)\n",j,dp1[1<<(j-1)].a,dp1[1<<(j-1)].b,j,dp2[1<<(j-1)].a,dp2[1<<(j-1)].b); } LL as = 0; for(int k2 = 1;k2 <= tp;k2 ++) { for(int k1 = 0;k1 <= tp;k1 ++) { sz res = merg(DP1(k1),DP2(k2));// if(k1 == 6) printf("( [%d%d]:%d(mod %d) )\n",k1,k2,res.a,res.b); if(res.b == 0 || res.a > (n-1)/a[i]) continue; if((ct[k1]+ct[k2])&1) (as += ANS1(res,a[i])) %= MOD; else (((as -= ANS1(res,a[i])) %= MOD) += MOD) %= MOD;// printf("[%d%d]:%d(mod %d)\n",k1,k2,res.a,res.b); } } (ans += as) %= MOD;// printf("%d\n",ans); memset(f2,0,sizeof(f2)); for(int j = 1;j < i;j ++) { if(gcd(a[i],a[j]) == 1) { LL x,y; exgcd(a[i],a[j],x,y); x = (x % a[j] + a[j]) % a[j]; dp2[1<<(j-1)] = sz(x,a[j]); } else dp2[1<<(j-1)] = sz(); f2[1<<(j-1)] = 1;// printf("dp2[%d]=%d(%d)\n",j,dp2[1<<(j-1)].a,dp2[1<<(j-1)].b); } as = 0; for(int k2 = 1;k2 <= tp;k2 ++) { for(int k1 = 0;k1 <= tp;k1 ++) { sz res = merg(DP1(k1),DP2(k2));// if(k1 == 6) printf("( [%d%d]:%d(mod %d) %d(mod %d))\n",k1,k2,d1.a,d1.b,d2.a,d2.b); if(res.b == 0 || res.a > n/a[i]) continue; if((ct[k1]+ct[k2])&1) (as += ANS2(res,a[i])) %= MOD; else (((as -= ANS2(res,a[i])) %= MOD) += MOD) %= MOD;// printf("[%d%d]:%d(mod %d)\n",k1,k2,res.a,res.b); } } (ans += as) %= MOD;// printf("%d\n",ans); } for(int i = 1;i <= m;i ++) { if(n % a[i] == 0) flag = 0; if((n-1) % a[i] == 0) flag2 = 1; } if(flag && flag2) ans ++; printf("%d\n",ans); return 0;}

转载地址：https://blog.csdn.net/weixin_43960414/article/details/110392058 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：[多校 NOIP 联合模拟 20201130 T4] ZZH 的旅行（斜率优化dp，启发式合并，平衡树）

下一篇：「雅礼集训 2017 Day2」线段游戏（线段树懒标记“启发式下传”，李超树）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题面