专栏文章

CF1747E 题解

cchenzhiyv
CF1747E题解参与者 1已保存评论 0

文章操作

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

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

CF1747E 题解

题意比较明确，不再复述。

分析

这道题给了两个数列，并且同一个数列之间有限制关系，不同数列之间也有限制关系，直接下手没有什么思路，考虑转化。
看到有两个数列，且互相限制很弱，考虑搬上网格图，将一对 (ai,bi)(a_i,b_i) 看作坐标，所有路径从 (0,0)(0,0) 出发 (n,m)(n,m) 结束，这样我们就将一个数列转化为了网格图上的一个路径。但这个转化是否好呢？我们代入原来的性质来验证：
  1. 原数列第一项为 (0,0)(0,0)，最后一项为 (n,m)(n,m) 变为路径从 (0,0)(0,0) 开始，(n,m)(n,m) 结束。
  2. 原数列单调不降变为路径只能向上走或向右走（假定 (0,0)(0,0) 在左下角，(n,m)(n,m) 在右上角）。
  3. ∀i∈[2,len] ai+bi≠ai−1+bi−1\forall i \in [2,len] \ a_i+b_i \neq a_{i-1}+b_{i-1} 变为不能有相同的两个点在同一条路径上。
至此，我们转化了原题，且没有丢失原题的性质，所以这是一个成功的转化。
然后我们来看这道题变成了什么：现在我们要求所有路径，在上面选点，问所有能够选出来的本质不同的点集的大小和。
我们定义使路径方向发生改变的点叫做拐点。容易发现，拐点可以分为两类，一类是使路径从右变上，一类是使路径从上变右。我们发现，当我们确定了这两类拐点中的一类拐点时，这一条路径就被唯一确定了（相邻两个拐点类似于一个正方形固定了对角的两个点，所以这个正方形就被唯一确定了，所以这两个点的路径也就被唯一确定了）。
接下来我们所说的拐点指使路径从右变上的拐点。
所以，我们将路径上的点分类，起点和终点分为一类（下图中橙色的点），拐点分为一类（下图中绿色的点），除此之外的所有点分为一类（下图中蓝色的点）。
对于拐点，它的横坐标取值范围是 [1,n][1,n]，纵坐标的取值范围是 [0,m−1][0,m-1]，所以当有 ii 个拐点时，一共有 (ni)(mi) \binom {n}{i} \binom {m}{i} 种取值，即有 ∑i=0min⁡(n,m)(ni)(mi)\sum_{i=0}^{\min(n,m)} \binom {n}{i} \binom {m}{i} 种路径
对于一条路径，这条路径上的拐点是必须要选的，否则无法唯一确定一条路径，同时要经过起点与终点，所以这一部分至少有 i+2i+2 的贡献(ii 是拐点数量)。对于路径上的非拐点，选不选都可以，一共有 2s2^s 种选择，ss 是非拐点数量，s=n+m+1−(i+2)=n+m−i−1s=n+m+1-(i+2)=n+m-i-1
对于非拐点，贡献为 ∑i(si)i\sum_i \binom{s}{i}i。这个东西等于 s2s−1s2^{s-1}(见oi-wiki组合数性质（8）)
所以，对于一条路径，总贡献为 2s(i+2)+s2s−12^s (i+2) + s 2^{s-1}
答案为 ∑i=0min⁡(n,m)(ni)(mi)∗(2s(i+2)+s2s−1)\sum_{i=0}^{\min(n,m)} \binom{n}{i} \binom{m}{i} * ( 2^s(i+2) + s 2^{s-1} )
代码：
CPP
#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=5e6+10,mod=1e9+7;
int fac[N],infac[N],pw[N<<1ll];
int qpow(int a,int b)
{
	if(b<0)
		return 0;
	int res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void init(int n)
{
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
	infac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=1;i--)
		infac[i]=infac[i+1]*(i+1)%mod;
	pw[0]=1;
	for(int i=1;i<=(n<<1ll);i++)
		pw[i]=pw[i-1]*2%mod;
}
int C(int n,int m)
{
	if(m>n)
		return 0;
	return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
int n,m;
int calc(int s)
{
	if(s==0)
		return 0;
	else
		return s*pw[s-1]%mod;
}
void solve()
{
	cin>>n>>m;
	int ans=0;
	for(int i=0;i<=min(n,m);i++)
	{
		int s=n+m-i-1;
		ans=(ans+C(n,i)*C(m,i)%mod*(pw[s]*(i+2)%mod+calc(s))%mod)%mod;
	}
	cout<<ans<<endl;
}
signed main()
{
	init(N-10);
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

评论

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

正在加载评论...