定制网站开发方案ppt,网站建设行业咨讯文章,客户关系管理系统简称,wordpress站点赏析题意 思路
正难则反
反过来需要考虑的是#xff1a;
(1) 所有满条件一的(x,y)有多少对#xff1a;
x 0 时#xff0c;有c1对 x 1 时#xff0c;有c对 ...... x c 时#xff0c;有1对
以此类推 一共有 (c2)(c1)/2 对
(2) 符合 x y ∈ S的有多少对#xff1a…题意 思路
正难则反
反过来需要考虑的是
(1) 所有满条件一的(x,y)有多少对
x 0 时有c1对 x 1 时有c对 ...... x c 时有1对
以此类推 一共有 (c2)(c1)/2 对
(2) 符合 x y ∈ S的有多少对
那就是x y ai 对 x 0 而言 y有固定的一种取值ai
但是要保证的是 y c 所以有 c - x 1
而x: 0-ai 所以对每一个ai有 ai/2 1种
(3) 符合 y - x ∈ S 的有多少对
y - x ai
那么 y ai x c
y ∈ [x,c-a[i]] 而x是从0开始的 所以每一个ai 都有 c - a[i] 1 种的情况
(4) 符合 (2) (3)的有多少对
x y ai
y - x aj
y (ai aj) / 2 所以要保证的是只有同奇偶性 才有这种情况
比如 奇数有{1,3,5}那么其实是C(2,3) 3 那就是 n(n-1)/2 n n(n1)/2
答案就是 odd(odd1) / 2 even(even1) / 2
(LAST ) ALL IN ALL
根据容斥定理 res (1) - (2) - (3) (4)
#includeiostream
#includecstdio
#includestack
#includevector
#includealgorithm
#includecmath
#includecstring
#includemap
#includeset
#includevector
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pairint,int PII;
const int INF 1e18 10;
const int N 1e5 10;
const int M 1e7 10;// 节点数量 3e6就够了是为什么
const int mod 1e9 7;
int n, m, k, x, now, ans;
int qcal(int a, int b) { int res 1; while (b) { if (b 1) res res * a % mod; b 1; a a * a % mod; } return res; }
int a[N], b[N];
bool is_prime(int n){if (n 2) return false; for (int i 2; i n / i; i){if (n % i 0){return false;}}return true;}
void gzy()
{int c;cin n c;int ans (1 c) * (2 c) / 2;int odd 0,even 0;for(int i 1;i n;i ){cin x;ans - x / 2 1;ans - (c - x 1);if(x % 2 0) odd ;else even ;}ans (odd 1) * odd / 2;ans (even 1) * even / 2;cout ans endl;
} signed main()
{int _ 1; cin _;while (_--) gzy();return 0;
}
// /**
// * ┏┓ ┏┓
// * ┏┛┻━━━┛┻┓
// * ┃ ┃
// * ┃ ━ ┃
// * ████━████
// * ◥██◤ ◥██◤
// * ┃ ┻ ┃
// * ┃ ┃
// * ┗━┓ ┏━┛
// * ┃ ┃ Code is far away from
// * ┃ ┃ bug with the animal protecting
// * ┃ ┗━━━┓ 神兽保佑,代码无bug
// * ┃ ┣┓
// * ┃ ┏┛
// * ┗┓┓┏━┳┓┏┛
// * ┃┫┫ ┃┫┫
// * ┗┻┛ ┗┻┛
// */
