【JZOJ6210】【20190612】wsm

题目

定义两个非递减数列的笛卡尔和数列$C = A \oplus B$ 为$(A_i+B_j)$排序后的非递减数列

$W$组询问，问有多少对可能的数列，满足:

$|C|=s,|A| = m,|B|=s/m$且$A \oplus B = C,C = \{ 0,1,\cdots,s-1 \}$

$1 \le W \le 500 \ , \ 1 \le s , m \le 10^{12} \ , \ 且 m \ | \ s $

题解

这题不好做的原因在于猜不到第一步，暂时还不会证明，证明的瓶颈在于能否证明对于给定一个合法序列A，它的最小的合法序列B满足$|B| \le |A|$ ，尝试了以晚上无果。。。。
合法的序列$A \ B$的布尔序列的生成方式:

初始时一定都存在$0$为$A , B \ = \ \{ 1 \}$ ，接下来有两种操作：

1.将$A$复制若干遍，$B$用全$0$补到相同长度

2.将$B$复制若干边，$A$用全$0$补到相同长度

1/2开始，交替进行12即可得到所有的合法序列对
讨论12进行的次数之后问题显然对于两维是独立的，变成从1 每次乘以一个非1的数到m的步数
对每个质因子用隔板法统计答案，容斥掉某些位置为1 的情况

时间复杂度：$O(W\sqrt N log \ s)$

#include<bits/stdc++.h>

#define mod  998244353

#define ll long long

using namespace std;

const int N=62;

ll n,m;

int ny[N<<1],fac[N<<1],inv[N<<1],d[N],A[N],B[N],ans;

void pre(){

	ny[1]=1;for(int i=2;i<=120;++i)ny[i]=1ll*(mod-mod/i)*ny[mod%i]%mod;

	for(int i=fac[0]=inv[0]=1;i<=120;++i)

		fac[i]=1ll*fac[i-1]*i%mod,

		inv[i]=1ll*inv[i-1]*ny[i]%mod;

}

void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}

void dec(int&x,int y){x-=y;if(x<0)x+=mod;}

int cal(int x,int y){return x<y?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}

void add(int*a,int x){for(int i=1;i<=60;++i)a[i]=1ll*a[i]*cal(x+i-1,i-1)%mod;}

void solve(ll x,int*a){

	for(int i=1;i<=60;++i)a[i]=1;

	for(int i=2;1ll*i*i<=x;++i)if(x%i==0){

		int tot=0;while(!(x%i)&&(x/=i))tot++;

		add(a,tot);

	}

	if(x!=1)add(a,1);

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

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

		dec(a[i],1ll*cal(i,j)*a[j]%mod);

}

int main(){

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

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

	int T;scanf("%d",&T);

	pre();

	while(T--){

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

		n/=m;if(n==1||m==1){puts("1");continue;}

		solve(n,A);

		solve(m,B);

		ans=0;

		for(int i=1;i<=60;++i)inc(ans , (2ll*A[i]*B[i]+1ll*A[i+1]*B[i]+1ll*A[i]*B[i+1]) %mod);

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

【JZOJ6210】【20190612】wsm

题目

题解

最新文章

热门文章