提高A组模拟划分

卧薪尝胆，厚积薄发。

提高A组模拟划分

Date: Fri Aug 10 22:44:18 CST 2018

In Category: NoCategory

Description：

序列 $x$ 长度为 $n$ 。它的 $K$ -划分序列 $y$ 指的是每连续 $K$ 个数的和得到划分序列，若只确定 $x$ 的 $K[1]$ 划分序列以及 $K[2]$ 划分序列.... $K[M]$ 划分序列的值情况下，问她可以确定 $x$ 多少个元素的值。

$n\le 10^9$ $m \le 10$

Solution：

发现一个位置 $i$ 的值能确定当且仅当知道前缀和 $s[i]$ 和 $s[i-1]$ 的值，于是问题就变成了问 $[1,n]$ 中有几个数满足存在 $p\ mod\ k[i]=0$ 且存在 $p\ mod\ k[j]=1$ ，即 $p=k[i]\times x=k[j]\times y+1$ ，即 $k[i]\times x-k[j]\times y=1$ 可以用扩展欧几里得求所有的正整数解。当且仅当 $gcd(k[i],k[j])=1$ 时有解，但是这样显然会算重，发现 $m$ 很小，设 $f[s_1][s_2]$ ， $s_1$ 表示 $p\ mod\ k[i]=0$ 的集合， $s_2$ 表示 $p\ mod\ k[j]=1$ 的集合，发现这个状态等价于 $p\ mod\ lcm(k[i1],k[i2],\dots)=0$ ， $p\ mod\ lcm(k[j1],k[j2],\dots)$ ，可以向上边一样用扩展欧几里得求，发现状态 $f[s_{1,1}][s_{1,2}]$ 和 $f[s_{2,1}][s_{2,2}]$ 会算重 $f[s_{1,1}\cup s_{2,1}][s_{2,1}\cup s_{2,2}]$ ，于是把 $f[s_{1,1}][s_{1,2}]$ 和 $f[s_{2,1}][s_{2,2}]$ 都减掉 $f[s_{1,1}\cup s_{2,1}][s_{2,1}\cup s_{2,2}]$ ，最后把这三部分都统计到答案里就能保证不重不漏了，具体实现是枚举 $s_1$ 和 $s_2$ 的子集并减掉 $f[s_1][s_2]$ ，注意循环时要倒序循环。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,m;

#define MAXN 11

ll k[MAXN];

ll f[1 << MAXN][1 << MAXN];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

ll lcm(ll a,ll b){return a / gcd(a,b) * b;}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b == 0)

	{

		x = 1;y = 0;

		return a;

	}

	ll t = exgcd(b,a % b,y,x);

	y -= a / b * x;

	return t;

}

ll ask(ll a,ll b)//x%a=0 x%b=1 k1a-k2b=1

{

	if(gcd(a,b) != 1 || (a == 1 && b == 1))return 0;

	ll x,y;

	exgcd(a,b,x,y);

	int cnt = 0;//cout << a << " " << b << " : " << endl;

	y = -y;b = -b;

	while(y <= 0 || x <= 0){x -= b;y += a;}

	int c1,c2;

	while(x + b >= 1 && y - a >= 1){x += b;y -= a;}

	b = -b;

	c1 = (n / a) / b;c2 = (n / b) / a;

	cnt = min(c1,c2);

	x += cnt * b;y += cnt * a;

	while(x * a <= n && y * b <= n)

	{

		++cnt;

		x += b;y += a;

	}//cout << cnt << endl;

	return cnt;

}

bool tag[1 << MAXN];

int main()

{

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

	freopen("sazetak.out","w",stdout);

	scanf("%lld%lld",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%lld",&k[i]);

	}

	k[++m] = n;

	int tot = (1 << m) - 1;

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

	{

		for(int j = 1;j <= tot;++j)

		{

			if(i & j)continue;

			ll a = 1,b = 1;

			tag[i] = tag[j] = true;

			for(int p = 1;p <= m;++p)

			{

				if(i & (1 << (p - 1)))a = lcm(a,k[p]);

				if(j & (1 << (p - 1)))b = lcm(b,k[p]);

				if(a > n){tag[i] = false;break;}

				if(b > n){tag[j] = false;break;}

			}

			if(!tag[i] || !tag[j])continue;

			f[i][j] = ask(a,b);

		}

	}

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

	{

		if(!tag[i])continue;

		for(int j = tot;j >= 1;--j)

		{

			if(i & j || !tag[j])continue;

			for(int ii = i;ii != 0;ii = ((ii - 1) & i))

			{

				if(!tag[ii])continue;

				for(int jj = j;jj != 0;jj = ((jj - 1) & j))

				{

					if(!tag[jj])continue;

					if(ii == i && jj == j)continue;

					f[ii][jj] -= f[i][j];

				}

			}

		}

	}

	ll ans = 0;

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

	{

		if(!tag[i])continue;

		for(int j = 1;j <= tot;++j)

		{

			ans += f[i][j];

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 数学-扩展欧几里得数学-容斥原理数学-同余

wjh15101051