首页 > 其他分享 >Codeforces Round 964 (Div. 4)

Codeforces Round 964 (Div. 4)

时间:2024-08-13 20:48:59浏览次数:5  
标签:964 uinv int inv Codeforces b1 b2 Div mod

### A.
```c++ #include<bits/stdc++.h> using namespace std;
const int N = 1e6 + 7; void solve() {     int x;     cin >> x;     cout << x / 10 + x % 10 << endl; } int main() {     int T;     cin >> T;     while(T --) solve(); } ```
### B. 四种情况分类讨论 ```c++ #include<bits/stdc++.h> using namespace std;
const int N = 1e6 + 7; void solve() {     int a1, a2, b1, b2;     cin >> a1 >> a2 >> b1 >> b2;     int cnt = 0;     if(a1 > b1 && a2 >= b2) cnt ++;     if(a2 > b1 && a1 >= b2) cnt ++;     if(a1 > b2 && a2 >= b1) cnt ++;     if(a2 > b2 && a1 >= b1) cnt ++;     cout << cnt << endl; } int main() {     int T;     cin >> T;     while(T --) solve(); } ```
### C.

### F.


设当前有 $p_0$ 个 0 和 $p_1$ 个 1,答案即为 $\sum_{i=0}^{\frac{k+1}{2}} \binom{p_0}{i} \binom{p_1}{k-i}$。
```c++ #include<bits/stdc++.h> #define int long long using namespace std;
const int N = 1e6 + 7; const int mod = 1e9 + 7; int p[N]; int inv[N], uinv[N]; int getc(int a, int b) {     if(a < b || b < 0) return 0;     return inv[a] % mod * uinv[b] % mod * uinv[a - b] % mod; } void solve() {     int p1 = 0, p0 = 0;     int n, k;     cin >> n >> k;     for(int i = 1; i <= n; i ++) cin >> p[i];     for(int i = 1; i <= n; i ++) {         if(p[i]) p1 ++;         else p0 ++;     }     int ans = 0;     for(int i = 0; i < (k + 1) / 2; i ++) {         ans += getc(p0, i) % mod * getc(p1, k - i) % mod;         ans %= mod;     }     cout << ans % mod << endl; } int qpow(int a, int b) {     int res = 1;     while(b) {         if(b & 1) res = res * a % mod;         b >>= 1;         a = a * a % mod;     }     return res % mod; } signed main() {     inv[0] = 1;     for(int i = 1; i < N; i ++) inv[i] = inv[i - 1] * i % mod;     uinv[N - 1] = qpow(inv[N - 1], mod - 2);     for(int i = N - 1; i >= 1; i --) uinv[i - 1] = uinv[i] * i % mod;     int T;     cin >> T;     while(T --) solve(); } ```

标签:964,uinv,int,inv,Codeforces,b1,b2,Div,mod
From: https://www.cnblogs.com/wyyqwq/p/18357666

相关文章

  • 【做题记录】Codeforces Round 915 (Div. 2)/CF1905A-F
    @目录A.ConstructiveProblems(800)B.Begginer'sZelda(1100)C.LargestSubsequence(1400)D.CyclicMEX(2000)E.One-X(2400)F.FieldShouldNotBeEmpty(2600)提交记录A.ConstructiveProblems(800)注意到,对于\(n\timesn\)的矩阵,只需要把对角线全染黑即可。推广到\(......
  • Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance
    https://codeforces.com/contest/1881/problem/F不难发现一件事情,我们这里最后的答案所在的点是1和3号点。我们有没有发现一个性质:就是这两个点都是红点间的路径上的,而且最后的答案就是最长的红点间的距离的长度除以二上取整。那么,我们怎么找到最长的红点间的距离呢?很显......
  • P3964 [TJOI2013] 松鼠聚会
    题意给定\(n\)个点,求出一个点使得每个点到这个点的切比雪夫距离之和最小。思路首先,我们可以把题目中的切比雪夫距离转化为曼哈顿距离,因为我们知道形如\((x,y)\)点之间的曼哈顿距离等于\((x+y,x-y)\)点之间的切比雪夫距离,\((x,y)\)点之间的切比雪夫距离等于\(\le......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)标题CodeForces1999A.A+BAgain?时限1second空限256megabytes题目描述给定一个两位数的正整数\(n\),求其数字之和。输入第一行包含一个整数\(t\)(\(1\leqt\leq90\))——测试用例的数量。每个测试用例的唯一一行包含一个两位数的正......
  • AGC182 C - Sum of Number of Divisors of Product
    题目大意:求长度为1,2,...N,的好序列因数个数。好序列满足每个元素\(1\leqx\leqM\)\(N\leq1e18,M\leq16\)很容易想到维护所有好序列质因数的指数+1的乘积。\(\prodb_i,1\leqi\leq6\).考虑每个数对这个乘积的影响。假设我们只有2,3,5这三个质数,序列末端添加15,......
  • 965div2补题
    A.FindKDistinctPointswithFixedCenter思路简单构造,我居然在这个题上因为没看懂英文还有机翻英太过逆天导致我WA了好几发......ACcode:#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){intx,y,k;cin>>x>>y>>k;in......
  • EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) 补题记录(A~D1,E)
    A容易发现答案为\(\min(n,k)\min(m,k)\)。#include<bits/stdc++.h>#defineintlonglong#definepbpush_backusingnamespacestd;constintN=1000100;inta[N];signedmain(){intT;cin>>T;while(T--){intn,m,k;cin>>n&g......
  • Codeforces Round 963 (Div. 2)
    Preface有懒狗上周日的比赛拖到这周日才写博客,我不说是谁这场比赛的时候因为C数组没开两倍卡了1h最后写对拍才看出来,直接心态爆炸导致D没写完掉大分A.QuestionMarks签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>......
  • CF1998 div2 & abc366
    1CF1.1B被诈骗了。我们的构造要向“每个区间只有1个数不一样考虑”。1.2C比较难。但是出的好。注意到如果我们不删除中位数这个位置的数,那么那个数是一定的。所以我们可以把\(k\)加到最大的可以加的数上,统计答案就在这个数,然后二分算中位数即可。其它策略?我们可不......
  • Codeforces Round 965 (Div. 2) 题解
    个人难度顺序:A<D<B<C<E。A.FindKDistinctPointswithFixedCenter如果\(k\)是偶数,构造\((x_c+i,yc+i)\),其中\(-\frac{k}{2}\lei\le\frac{k}{2}\)。对于\(k\)是奇数,先加一个点\((xc,yc)\),然后就变成偶数的情况了。B.MinimizeEqualSumSubarr......