【思维】【多项式系数】CodeCraft-20 (Div. 2) C. Primitive Primes

• 博客主页: https://blog.csdn.net/qq_50285142
• 欢迎点赞收藏✨关注❤留言  如有错误，敬请指正
• 虽然生活很难，但我们也要一直走下去

题目链接

思路：
考虑 x i + j x^{i+j} xi+j的系数 c i + j c_{i+j} ci+j​
c i + j = ( a 0 ∗ b i + j + a 1 ∗ b i + j − 1 + . . . ) + a i ∗ b j + ( a i + 1 ∗ b j − 1 + a i + 2 ∗ b j − 2 + . . . ) c_{i+j} = (a_0 * b_{i + j} + a_1 * b_{i + j - 1} + ...) + a_i * b_j + (a_{i + 1} * b_{j - 1} + a_{i + 2} * b_{j - 2} +...) ci+j​=(a0​∗bi+j​+a1​∗bi+j−1​+...)+ai​∗bj​+(ai+1​∗bj−1​+ai+2​∗bj−2​+...)
我们找 f ( x ) f(x) f(x)系数中第一个%p不等于0的系数位置i， g ( x ) g(x) g(x)系数中第一个%p不等于0的系数位置j,那么 a i % p ≠ 0 ， b i % p ≠ 0 ， 得 a i ∗ b i % p ≠ 0 a_i %p ≠0，b_i % p≠0，得a_i*b_i %p≠0 ai​%p​=0，bi​%p​=0，得ai​∗bi​%p​=0

( a 0 ∗ b i + j + a 1 ∗ b i + j − 1 + . . . ) (a_0 * b_{i + j} + a_1 * b_{i + j - 1} + ...) (a0​∗bi+j​+a1​∗bi+j−1​+...)中的a系数都是p的倍数
( a i + 1 ∗ b j − 1 + a i + 2 ∗ b j − 2 + . . . ) (a_{i + 1} * b_{j - 1} + a_{i + 2} * b_{j - 2} +...) (ai+1​∗bj−1​+ai+2​∗bj−2​+...)中的b系数都是p的倍数
但是 a i ∗ b j a_i*b_j ai​∗bj​不是p的倍数，所以 x i + j x^{i+j} xi+j的系数不是p的系数

#include
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair pii;
typedef pair pll;
typedef vector vi;
typedef vector vl;
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const int N = 1e5+5,M = 2e5+5;

ll n,m,k,p;

void solve()
{
	cin>>n>>m>>p;
	bool is = true;
	int res1,res2;
	for(int i=0;i>x;
		if(is and x%p)
		{
			is = false;
			res1 = i;
		 } 
	 } 
	is = true;
	for(int i=0;i>x;
		if(is and x%p)
		{
			is = false;
			res2 = i;
		}
	}
	cout<>_;
	_ = 1;
	while(_--)
	{
		solve();
	}
	return 0;
}

• STL详解，超全总结(快速入门STL)
• 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）
• 区间贡献问题习题详解