JZOJ 5796 划分 （容斥，数论，扩展CRT）
题面
有一个未知的序列 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 1
2sample output #1
1sample input #2
6 2
2 3sample output #2
2sample input #3
123456789 3
5 6 9sample output #3
10973937sample input #4
4833827 4
7 8 9 10sample output #4
552436【样例解释】
【样例 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 分别要满足的条件为：
（初中的同学看过来：“
” 是 “存在” 的意思，即存在一个小于 i 的 j，满足...，“
” 是 “任意” 的意思，即对于任意的小于 i 的 j，满足...，大括号内两个条件要同时满足）
我们知道，对于每个 j < i ，如果分别求满足上述条件的 k 的数量，显然大概率会算重，而且并不是上面两个式子应有的解法，
但是，这样求又是最快的，怎么办呢，用容斥！
我们把大括号内两个条件分开，再把对于每个 j 的条件分开，一共得到 2 * (i-1) 个条件，然后枚举 种状态做容斥，下面那个 “
” 的式子，就可以把它变成 “
”的式子来算，这样更方便容斥。
对于只有一个条件的状态，我们很好算，但是对于很多条件的状态就显得困难，不急，我们继续推
上述两个大括号可以等价于：
把一些条件单独拿出来就是这样的形式：
这是个线性同余方程组，我们可以用扩展中国剩余定理来做，
最后求得了一个方程：
k 的数量就可以直接做除法了！
把两个大括号分别求贡献，
由于我用记忆化处理每个状态，每次算一个状态就只用算一次式子合并，时间复杂度（自己证一下吧）
CODE
记忆化直接递归，白爆60分，呜呼！
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
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;
}最新文章
- windows server 2008 wamp安装报000F15A0解决方法
- 安装指定版本的cordova
- arpg网页游戏之地图（二）
- Audrion小车实验过程
- CMD窗口正确显示UTF-8字符
- iOS项目里面如何清理缓存
- dubbo 线程池
- Pycharm安装并配置jupyter notebook
- Loadrunner进行HTTPS协议性能测试
- [转]data-driven与决策树聚类的两种方法
- C#-MVC开发微信应用(8)--菜单管理的实现
- golang 与 c语言 之间传递指针的规则提案
- python中的logger模块
- Failed to execute request because the App-Domain could not be created. Error: 0x80070002 系统找不到指定的文件。
- OpenStack 图形化服务 Horizon使用（十三）
- DevExpress v17.2新版亮点—Analytics Dashboard篇（一）
- Ubuntu 搭建Ghost1.0博客系统
- Socket相关函数(1)- socket(), bind(), listen(), accept(), connect(), TCP模型
- drupal7请求异常，执行时间过长的解决方法
- Java网络通信基础编程