新野企业网站建设,网站建设需要每年交钱吗,凉山州住房和城乡建设厅网站,网站制作哪家便宜2022 ICPC 济南 E. Identical Parity (扩欧)
Problem - E - Codeforces
大意#xff1a;给出一个 n 和一个 k #xff0c; 问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。
思路#xff1a;通过分析可知 #xff0c; 任两个间隔 k - 1 的元素奇偶…2022 ICPC 济南 E. Identical Parity (扩欧)
Problem - E - Codeforces
大意给出一个 n 和一个 k 问是否能构造一个长 n 的排列使得所有长 k 的连续子序列和的奇偶性相同。
思路通过分析可知 任两个间隔 k - 1 的元素奇偶性必然相同 这样的话 问题就转化成了 n % k 个 ⌊ n k ⌋ 1 和 k − n % k 个 ⌊ n k ⌋ 是否能组成 ⌊ n 2 ⌋ 和 n − ⌊ n 2 ⌋ 的问题 n ~\% ~k ~个\left \lfloor \frac{n}{k} \right \rfloor 1和k-n~\%~k个\left \lfloor \frac{n}{k} \right \rfloor是否能组成\left \lfloor \frac{n}{2} \right \rfloor和n - \left \lfloor \frac{n}{2} \right \rfloor的问题 n % k 个⌊kn⌋1和k−n % k个⌊kn⌋是否能组成⌊2n⌋和n−⌊2n⌋的问题
很自然的就可以想到 01 背包去解决这个问题 但是显然 n 和 k 的范围太大了 无法使用 01 背包去解决这个问题。 于是转化问题 考虑现有范围的 x 和 y 是否能满足以下式子。 ⌊ n k ⌋ 1 ∗ x ⌊ n k ⌋ ∗ y ⌊ n 2 ⌋ \left \lfloor \frac{n}{k} \right \rfloor 1*x~~\left \lfloor \frac{n}{k} \right \rfloor*y \left \lfloor \frac{n}{2} \right \rfloor ⌊kn⌋1∗x ⌊kn⌋∗y⌊2n⌋
带入扩欧得到通解 x x 0 ∗ c g c d ( a , b ) k ∗ b g c d ( a , b ) xx_0*{c\over gcd(a,b)}{k*b\over gcd(a,b)} xx0∗gcd(a,b)cgcd(a,b)k∗b y y 0 ∗ c g c d ( a , b ) − k ∗ a g c d ( a , b ) yy_0*{c\over gcd(a,b)}-{k*a\over gcd(a,b)} yy0∗gcd(a,b)c−gcd(a,b)k∗a
根据已有的 x 的范围 和 y 的范围分别求出两个 k 的范围 判断这两个区间是否相交即可。
易错点是否可以通过 x 的范围求出对应 k 的范围然后带入求 y 的范围 显然是可以的 但是这样求出的 y 的范围区间是不连续的 也就不能判交。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int n , t , k;int exgcd(int a , int b , int x , int y){if(b 0){ x 1; y 0; return a;}int g exgcd(b , a % b , y , x);y - a / b * x;return g;
}signed main(){IOScin t;while(t --){cin n k;if(n % k 0){int num n / k , od , ev;ev n / 2;od n - ev;if(ev % num 0 od % num 0){cout Yes \n;}else{cout No \n;}}else{int a n / k , b n / k 1 , c n / 2;int cntb n % k , cnta k - n % k;int x , y , gcds;gcds exgcd(a , b , x , y);a / gcds;b / gcds;c / gcds;int k1_max floor((double)(cnta - x * c) / (double) b);int k1_min ceil((double)(0 - x * c) / (double) b);int k2_max floor((double)(y * c) / (double) a);int k2_min ceil((double)(y * c - cntb) / (double) a); if(k1_min k1_max || k2_min k2_max){cout No\n;}else{if(min(k2_max , k1_max) max(k1_min , k2_min)){cout Yes\n;}else{cout No\n;}}}}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);
