【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(Wsqrt 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
  ",ans);
  	}
  	return 0;
  }