牛客小白月赛25
原题链接
[TOC]
##题外话
有点时间没打代码了， 本来就菜，现在快菜的只会hello world了
牛客比赛我就不写题意了
A
思路
我是找规律做的
-
-
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<ll,ll> pll;
//ll read(ll x=0)
//{
// ll c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =500010;
ll MOD =998244353998244353 ;
ll n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
ll br[N],ar[N];
ll i;
ll cmp (ll a , ll b){
return a>b;
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
ll x;
cin >>n>> x;
ll ma =0 ,mi = 0,sum =0 ;
rep(i,1,n)cin>>ar[i], ma= max(ma ,ar[i]),sum +=ar[i];
if(x==1)return cout<<ma*x<<endl, 0;
sort(ar+1 ,ar+1+n,cmp);
ll cnt =0 ,pos = x;
if(n<pos)return cout<<sum<<endl,0;
rep(i,1,pos-1){
cnt+=ar[i]-ar[pos];
}
cout<< cnt+ar[pos]*x<<endl;
return 0;
}
// 5
B
思路
（今天问了一下yk ， 发现昨天我的想法大体上没有错误，就是想复杂了）
-
-
-
-
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<LL,LL> pLL;
//LL read(LL x=0)
//{
// LL c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =500010;const int maxn = 200010;
LL P = 1e9+7 ;
LL n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
LL br[N],ar[N];
LL i,j,g;
const LL p = 1000000007;
LL f[maxn];
LL inv[maxn]; // 阶乘的逆元
LL Pow(LL a, LL n, LL m)
{
LL t = 1;
for (; n; n >>= 1, a = (a * a % m))
if (n & 1)
t = (t * a % m);
return t;
}
void CalFact()
{
f[0] = 1;
for (int i = 1; i < maxn; i++)
f[i] = (f[i - 1] * i) % p;
inv[maxn - 1] = Pow(f[maxn - 1], p - 2, p);
for (int i = maxn - 2; ~i; i--)
inv[i] = inv[i + 1] * (i + 1) % p;
}
LL C(int n, int m)
{
if(m < 0||m > n) return 0;
return f[n] * inv[m] % p * inv[n - m] % p;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
CalFact();
cin >> n >> m>>k;
int cnt = k/2;
LL ans = C(n-1,cnt-1)*C(m-1,k-cnt-1)%P+C(m-1,cnt-1)*C(n-1,k-cnt-1)%P;
cout<<ans%P<<endl;
return 0;
}
// 5
C
思路
我是照着题解写的，我就不献丑了（并查集和DFS已经不会写了TAT）
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<LL,LL> pLL;
//LL read(LL x=0)
//{
// LL c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =3000010;const int maxn = 200010;
LL p = 1e9+7 ;
LL n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
LL h[N],e[N*2],ne[N],idx =0 ;
LL fa[N] , kdm[N],sz[N];
void add ( LL a , LL b){
e[idx]=b, ne[idx]=h[a], h[a]=idx++ ;
}
vector<LL> w[N],b[N];
LL f(LL x){
if(fa[x]==x)return x ;
return f(fa[x]);
}
void un(LL a ,LL b ){
LL x =f(a) , y= f(b);
if(x!=y){
if(kdm[x]<kdm[y] ){
fa[x]=y;
kdm[y]+=kdm[x]+1;
}
else {
fa[y]=x;
kdm[x]+=kdm[y]+1;
}
}
}
LL br[N],ar[N];
LL i,j,g;
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
cin >>n;
string s ;cin >>s ;
for(i=1;i<=n;i++)fa[i]=i;
rep(i,1, n-1){
LL l,r;cin >>l>> r;
// add(l,r ),add(r, l);
w[l].push_back(r);
w[r].push_back(l);
if(s[l-1]=='W' &&s[r-1]=='W'){
un(l,r);
}
}
LL ma =0 ;
rep(i,1,n)if(s[i-1]=='W')sz[i]=kdm[f(i)]+1;
for(int i=1 ;i<=n;i++){
if(s[i-1]=='B'){
LL sum=1 ;
for(int j = 0;j<w[i].size();j++){
if(s[w[i][j]-1]=='W')sum+=sz[w[i][j]];
}
ma =max(sum ,ma );
}
}
if(ma==0)cout << n<<endl;
else cout<<ma<<endl;
return 0;
}
// 5
D
思路
- 来一波反向思维，找到每个抽不到的概率然后用1减去每个抽不到的概率的积就完事了 - 公式也就是$1-((a1-b1)/b1*(a2-b2)/b2*...)$ - 关于a/b这样的式子如何编程，用逆元就行了 - 咕噜灵波~
代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<LL,LL> pLL;
//LL read(LL x=0)
//{
// LL c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =1000010;const int maxn = 200010;
LL p = 1e9+7 ;
LL n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
LL br[N],ar[N];
LL i,j,g;
LL bin(LL x, LL n, LL MOD) {
n%=MOD-1;
LL ret = MOD != 1;
for (x %= MOD; n; n >>= 1, x = x * x % MOD)
if (n & 1) ret = ret * x % MOD;
return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >>n;
rep(i,1,n)cin >>ar[i];
rep(i,1,n)cin >>br[i];
LL sum = p, num =1 ;
rep(i,1,n){
num*= (ar[i]-br[i])%p*get_inv(ar[i],p)%p;
num%=p;
// cout <<(ar[i]-br[i])%p<<" "<<get_inv(ar[i],p)%p<<endl;
}
//cout<<sum - num <<endl;
cout<<(p+(1-num))%p <<endl;
return 0;
}
// 5 E
思路
考虑用栈，或者用erase从后往前删除
###代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
long long a[28];
int main()
{
string s;
cin >> s;
string ans;
for(auto &x : s)
{
if(ans.size() == 0)
{
ans+=x;
continue;
}
while(ans.size())
{
char c = ans[ans.size() - 1];
if(c == x)
{
ans.pop_back();
break;
}
else{
ans+=x;
break;
}
}
}
if(ans.size() == 0)cout << 0 << endl;
else cout << ans << endl;
return 0;
} F
思路
有多少个隐藏的，最小部分就加多少1，最大部分就加多少5（不会有人不会把，不会吧不会吧）
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<ll,ll> pll;
//ll read(ll x=0)
//{
// ll c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =500010;
ll MOD =998244353998244353 ;
ll n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
double br[N],ar[N];
ll i;
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
cin >>n>>m ;
double sum =0 ;
rep(i,1,n-m)cin >>ar[i],sum +=ar[i];
if(n-m==0){
double mi =1,ma = 5;
printf("%.5f %.5f",mi,ma);
}
else {
double mi =sum ,ma =sum ;
rep(i,n-m+1,n){
mi+=1;
ma+=5;
}
printf("%.5f %.5f",mi/n,ma/n);
}
return 0;
}
// 5
G
思路
（自己像个憨憨一样给那解方程。。）
- 正解是通过观察这个方程的左边发现这个式子是个单调递增的，然后就会想起的要求是要单调递增，所以我们就用二分就行!
- 剩下就是二分的基本套路了，我就不写了，但注意一件事，这个用while（l<r）会超时，不知道为啥，所以用for循环1000次就行
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<LL,LL> pLL;
//LL read(LL x=0)
//{
// LL c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =1000010;const int maxn = 200010;
LL p = 1e9+7 ;
LL n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
LL br[N],ar[N];
LL i,j,g;
LL bin(LL x, LL n, LL MOD=p) {
n%=MOD-1;
LL ret = MOD != 1;
for (x %= MOD; n; n >>= 1, x = x * x % MOD)
if (n & 1) ret = ret * x % MOD;
return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
double f(double a, double b){
if(b==1)return a ;
else if(b==2)return a*a;
else return a*a*a;
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
long double a ,b ,c ;cin >>a>>b>>c;
double l =0 , r =10000000000000000;
rep(i,1,1000){
double mid =(l+r)/2;
if(f(mid,a)+b*log(mid)>c){
r =mid;
}
else l =mid ;
}
printf("%.8f",r);
return 0;
}
// 5
H
思路
用一下我代码里的东西就行，考察这个方式运行代码，没啥难度
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<ll,ll> pll;
//ll read(ll x=0)
//{
// ll c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =500010;
ll MOD =998244353998244353 ;
ll n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
ll br[N],ar[N];
ll i;
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
string s;
map<char , int >mp;
while(getline(cin,s)){
int len =s.size();
for(int i=0;i<len;i++){
if(s[i]==' ')continue ;
mp[s[i]]++;
}
}
int ma=0 ;char a;
for(auto &it:mp){
if(ma <it.se){
ma = it.se ;
a=it.fi;
}
}
cout<<a<<endl;
return 0;
}
// 5
I
思路
- 这个就是把每列和每行的数想加起来然后把对应的数字减去一次自身即可 - 注意不要用二维数组，因为不确定数组大小这样会爆掉，建议用vector的二维（这个是动态的，所以没有问题）
代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<ll,ll> pll;
//ll read(ll x=0)
//{
// ll c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =500010;
ll MOD =998244353998244353 ;
ll n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
ll br[N],cr[N];
ll i,j;
vector<ll >ar[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >>n>> m;
rep(i,1,n){
ar[i].push_back(0);
rep(j,1,m){
ll cnt =0;
cin >>cnt;
ar[i].push_back(cnt);
}
}
// br hang , cr lie
rep(i,1,n){
rep(j,1,m)br[i]+=ar[i][j];
}
rep(i,1,m){
rep(j,1,n)cr[i]+=ar[j][i];
}
rep(i,1,n){
rep(j,1,m){
cout<<br[i]+cr[j]-ar[i][j]<<" ";
}cout<<endl;
}
return 0;
}
// 5
J
思路
这个是套路题，就是找出每个数的每个数位的1的贡献，然后因为只有1,1,1和1,0,0符合要求所以只要找出这两中国情况乘上这个数位即可
###代码
#include <cstdio>
#include <algorithm>
#include<iomanip>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include<stack>
#include <cassert>
#include<map>
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define pb push_back
#define de(x) cerr<<#x<<" = "<<x<<endl
#define __i __int128
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
typedef pair<LL,LL> pLL;
//LL read(LL x=0)
//{
// LL c, f(1);
// for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
// for(;isdigit(c);c=getchar())x=x*10+c-0x30;
// return f*x;
//}
const int N =1000010;const int maxn = 200010;
LL p = 1e9+7 ;
LL n , k , m ;
void clear(unsigned char *pta, int size )
{
while(size>0)
{
*pta++ = 0;
size --;
}
}
LL br[N],ar[N];
LL i,j,g;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >>n;
LL cnt=0 ;
rep(i,1,n){
LL num ;cin >>num;
cnt =0 ;
while(num){
if(num&1)br[cnt]++ ;
cnt ++ ;
num >>=1 ;
}
}
LL sum =0;
rep(i,0,64){
// cout <<br[i]*(br[i]-1)*(br[i-2])/6%p<<" "<<(n-br[i])*(n-br[i]-1)/2*br[i]%p<<endl;
sum +=(1LL<<i)%p*(br[i]*(br[i]-1)*(br[i]-2)/6%p+(n-br[i])*(n-br[i]-1)/2*br[i]%p);
sum %=p;
}
cout<<sum%p <<endl;
return 0;
}
// 5
