专栏文章

UVA12633 Super Rooks on Chessboard

rroger_yrj
UVA12633题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqmpjq3
此快照首次捕获于
2025/12/04 07:19
3 个月前
此快照最后确认于
2025/12/04 07:19
3 个月前
查看原文

UVA12633 Super Rooks on Chessboard

前言

这有黑？纯纯细节题。

题解

很容易想到容斥。设能被行攻击的格子集合为 RR，能被列攻击的格子集合为 CC，能被对角线攻击的格子集合为 DD，那么答案就为 n×m−∣R∣−∣C∣−∣D∣+∣R∩C∣+∣C∩D∣+∣D∩R∣−∣R∩C∩D∣n\times m-|R|-|C|-|D|+|R\cap C|+|C\cap D|+|D\cap R|-|R\cap C\cap D|，唯一的难点是求 ∣R∩C∩D∣|R\cap C\cap D|。
对于一条对角线，xx 与 yy 的差是相同的，我们用 x−yx-y 表示一条对角线的标号。设 rir_i 被行攻击， cic_i 被列攻击， did_i 被对角线攻击。求 ∣R∩C∩D∣|R\cap C\cap D| 就是求多少个 (i,j,k)(i,j,k) 使得 ri−cj=dkr_i-c_j=d_k，移项为 ri=dk+cjr_i=d_k+c_j。
构造生成函数 F(x)∑i∈dxi,G(x)∑i∈cxiF(x)\sum\limits_{i\in d}x^i,G(x)\sum\limits_{i\in c}x^i，答案为 ∑i∈r[xi]F∗G(x)\sum\limits_{i\in r}[x^i]F*G(x)。
直接 FFT/NTT 即可

代码

写的比较乱，尽量不要参考
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e6+10,mod=998244353;
int f[N],g[N],n,m,l,r[N],vis1[N],vis2[N],vis3[N],sum1[N],sum2[N];
int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}
void NTT(int *a,int op){
	for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int i=1;i<n;i<<=1){
		int wn=qpow(op==1?3:332748118,(mod-1)/(i<<1));
		for(int j=0;j<n;j+=(i<<1)){
			int w=1;
			for(int k=0;k<i;k++,w=1ll*w*wn%mod){
				int x=a[j+k],y=1ll*w*a[j+k+i]%mod;
				a[j+k]=(x+y)%mod;
				a[j+k+i]=(x-y+mod)%mod;
			} 
		}
	}
}
void init(){
	memset(sum1,0,sizeof(sum1));
	memset(sum2,0,sizeof(sum2));
	memset(vis1,0,sizeof(vis1));
	memset(vis2,0,sizeof(vis2));
	memset(vis3,0,sizeof(vis3));
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));l=-1;
}
void solve(int T){
	init();
	int t;
	cin>>n>>m>>t;
	ll ans=-1ll*n*m;
	for(int i=1,x,y;i<=t;i++){
		cin>>x>>y;
		vis1[x]=vis2[y]=vis3[x-y+m]=1;
	}
	for(int i=1;i<=n;i++)if(vis1[i])ans+=m;
	for(int i=1;i<=m;i++)if(vis2[i])ans+=n;
	for(int i=1;i<=n+m;i++)if(vis3[i])ans+=min(i,n)-max(i+1-m,1)+1;
	for(int i=1;i<=n;i++)sum1[i]=vis1[i]+sum1[i-1];
	for(int i=1;i<=m;i++)sum2[i]=vis2[i]+sum2[i-1];
	ans-=1ll*sum1[n]*sum2[m];
	for(int i=1;i<=n+m;i++)if(vis3[i])ans-=sum1[min(i,n)]-sum1[max(i+1-m,1)-1];
	for(int i=1;i<=n+m;i++)if(vis3[i])ans-=sum2[min(n-i+m,m)]-sum2[max(1-i+m,1)-1];
	for(int i=1;i<=m;i++)if(vis2[i])f[i]=1;
	for(int i=1;i<=n+m;i++)if(vis3[i])g[i]=1;
	int n_=n,m_=m;
	m=n+m+m;n=1;
	while(n<=m)n<<=1,l++;
	for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l);
	NTT(f,1),NTT(g,1);
	for(int i=0;i<n;i++)f[i]=1ll*f[i]*g[i]%mod;
	NTT(f,-1);
	int inv=qpow(n,mod-2);
	for(int i=0;i<n;i++)f[i]=1ll*f[i]*inv%mod;
	for(int i=1;i<=n_;i++)ans+=1ll*vis1[i]*f[i+m_];
	cout<<"Case "<<T<<": "<<-ans<<"\n";
}
int main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++)solve(i);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...