D

题目链接 D小红的区间查询

思路

本题要求 中 的个数，我们想让变量只在分母或者分子，变化下原式有：

那么就是找 ，即b-a的所有因数中在范围内的有几个

我们直接预处理 的所有因数然后push_back() 进d里面，二分找到>=L以及<=R的下标，最后相减就行。（这里的 ）

代码

const int MAXN=200005;
vector<int> d[MAXN];
vector<int> cnt;

// 这里用筛法先求出所有的因数
// 当然也可以用O(n\sqrt(n))的常规方法

/*
void init()
{
    for(int j=1; j<MAXN; j++)
    {
        for(int i=1; i*i<=j; i++)
        {
            if(j%i==0)
            {
                d[j].push_back(i);
                if(i*i!=j) d[j].push_back(j/i);
            }
        }
        sort(d[j].begin(), d[j].end()); 
    }
}
*/

void init()
{
    for(int i=1; i<MAXN; i++)
    {
        for(int j=i; j<MAXN; j+=i)d[j].push_back(i);
    }
}


void sol()
{
	ll a,b,l,r; cin >> a >> b >> l >> r;
	ll z=b-a;
	ll st=l-b, ed=r-b;
	if(st>z)
	{
		cout << 0 << endl;
		return;
	}
	vector<int> &t=d[z];
	auto il=lower_bound(t.begin(), t.end(), st)-t.begin();
	auto ir=upper_bound(t.begin(), t.end(), ed)-t.begin();
	cout << ir-il << endl;
}

E

链接 小红的gcd

思路

我们先看这个题目要求的连续K个"g或者c或者d"以及只能向右和向下的路径右有什么规律，首先无论怎么走，路径长度 ，那么最终的字符串就会变成 个"g或者c或者d"。

显然地，对于此类路径统计问题dp往往能很好地解决，我们设 dp[i][j][s] 为前i行j列中满足s规则的路径数，其中s的规则是gcd字符串的全排列，那么其转移方程是：dp[i][j][s]=(dp[i-1][j][s]+dp[i][j-1][s])%MOD ，当然必须满足坐标为 时规则s所对应的字符。

而坐标 时其对应的路径长度 那么此时对应的s规则中的字符应该是第 个，满足这个条件才能继承上一个dp

最后统计下所有s的情况下dp[n][n][s]的和即可

代码

const int MOD=998244353;
const char srule[6][3]={
	{'g','c','d'},
	{'g','d','c'},
	{'c','g','d'},
	{'c','d','g'},
	{'d','c','g'},
	{'d','g','c'}
};

void sol()
{
	int n;cin >> n;
	vector<string> a(n);
	for(auto &x:a)cin >> x;
	if((2*n-1)%3!=0)
	{
		cout << 0 << endl;
		return;
	}
	int dp[n+1][n+1][6]={0};
	int p=(2*n-1)/3;
	for(int s=0; s<6; s++)
	{
		if(a[0][0]=srule[s][0])dp[1][1][s]=1;
	} // 这里一定要先设置初始值，debug 20min+的教训
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i==1 && j==1)continue;
			int L=i+j-1;
			int idx=(L-1)/p; // s坐标是0开头
			char cur=a[i-1][j-1];
			// pnt2(L,idx);
			for(int s=0; s<6; s++)
			{
				char need=srule[s][idx];
				// pnt2(need,cur);
				// pnt2(i,j);
				if(cur==need)
				{
					if(i>1)(dp[i][j][s]+=dp[i-1][j][s])%=MOD;
					// else dp[i][j][s]=1;
					if(j>1)(dp[i][j][s]+=dp[i][j-1][s])%=MOD;
					// else dp[i][j][s]=1;
					dp[i][j][s]%=MOD;
				}
			}
		}
	}
	int ans=0;
	for(int i=0; i<6; i++)(ans+=dp[n][n][i])%=MOD;
	cout << ans << endl;
}