牛客|牛客练习赛76 acm|c++|牛客

牛客练习赛76 A 校园活动枚举每组的和即可

#include //#pragma GCC optimize(2) #define int long long using namespace std; //const int mod = 998244353; const int mod = 1e9 + 7; const int maxn = 1e3 + 10; int a[maxn]; void solve() {int n; string s; cin>>n>>s; int sum=0; for (int i = 1; i <=n; ++i) {a[i]=s[i-1]-'0'; sum+=a[i]; } if(sum==0){cout<j){flag=0; break; } } if (flag) {cout<> _; while (_--) {solve(); } return 0; }

C CG的通关秘籍

文章图片

#include //#pragma GCC optimize(2) #define int long long using namespace std; //const int mod = 998244353; const int mod = 1e9+7; const int maxn = 2e5 + 10; int fastpow(int a,int n){int temp=a; int res=1; while (n){if(n&1) res=res*temp%mod; temp=temp*temp%mod; n>>=1; } return res; }void solve() {int n,m; cin>>n>>m; int gx=m*(3*m-3)/2%mod*(n-1)%mod; cout<> _; while (_--) {solve(); } return 0; }

E 牛牛数数线性基，这是一种能够求给定序列异或第 k小的东西
二分答案 ans, 将线性基里面第 ans 小的元素与给定 x 作比较，大于则符合条件，由此二分出最小的符合条件的 ans，那么答案就是 sum - ans + 1, sum 是线性基的集合大小。

#include #define int long long using namespace std; const int maxn = 1e5 + 5; const int mod = 77797; const int MAXL = 63; struct LinearBasis {long long a[MAXL + 1]; int cnt; LinearBasis() {std::fill(a, a + MAXL + 1, 0); }LinearBasis(long long *x, int n) {build(x, n); }int insert(long long t) {for (int j = MAXL; j >= 0; j--) {if (!t) return 0; if (!(t & (1ll << j))) continue; if (a[j]) t ^= a[j]; else {for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k]; for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t; a[j] = t; return 1; } } return 0; }// 数组 x 表示集合 S，下标范围 [1...n] void build(long long *x, int n) {std::fill(a, a + MAXL + 1, 0); for (int i = 1; i <= n; i++) {cnt+=insert(x[i]); } }long long queryMax(int k) {long long res = 0; for (int i = 0; i <= MAXL; i++) if ((k>>i)&1) res ^= a[i]; return res; } }lb; int b[maxn]; void solve() {int k, n; cin >> n >> k; for (int i = 1; i <= n; ++i) {cin>>b[i]; } lb.build(b,n); for (int i = 0, j = 0; i <= 62; ++i) if (lb.a[i]) lb.a[j++] = lb.a[i]; int l = 0, r = (1ll << lb.cnt) - 1; while (l < r) {int mid = l + r + 1 >> 1; if (lb.queryMax(mid) > k) r = mid - 1; else l = mid; } cout << (1ll << lb.cnt) - l - 1; }signed main() {int _ = 1; //cin>>_; while (_--) {solve(); } return 0; }

F phi and phi 莫比乌斯反演，差分

文章图片

文章图片

【牛客|牛客练习赛76】欧拉函数

文章图片

#include //#pragma GCC optimize(2) #define int long long using namespace std; //const int mod = 998244353; const int mod = 1e9 + 7; const int maxn = 1e6 + 10; int vis[maxn*3]; int prime[maxn*3]; int phi[maxn*3]; int ans[maxn*3]; int num; void init(){phi[1]=1; num=0; for (int i = 2; i < maxn; ++i) {if (!vis[i]){prime[++num]=i; phi[i]=i-1; } for (int j = 1; j <=num&&i*prime[j]>n; for (int T = 1; T <=n; ++T) {int sum=0; for (int i = 1; i <=n/T; ++i) {sum=(sum+phi[i*T])%mod; ans[i*T]=(ans[i*T]+phi[T]*sum%mod*sum%mod+mod)%mod; ans[(i+1)*T]=(ans[(i+1)*T]-phi[T]*sum%mod*sum%mod+mod)%mod; } } for (int i = 1; i <=n; ++i) {ans[i]=((ans[i]+ans[i-1])%mod+mod)%mod; cout<> _; while (_--) {solve(); } return 0; }