首页 > 其他分享 >2024牛客多校第一场

2024牛客多校第一场

时间：2024-07-18 11:12:36浏览次数：6  
标签：return int sum 多校 ret cin 2024 牛客 long

A

简单的组合数学。考虑枚举为1的个数的长度为x，则其他数除了最后一位的0外都可以乱填。

对于末尾为1的数，显然每一位都是独立的，单独考虑每一位。

显然只要该位上有一个0即可，经典容斥：减去全为1的这一种情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=5005;
int f[N][N];
int qpow(int a,int b,int mod){
    int ret=1;
    while(b){
        //TODO
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
signed main(){
    int n,m,p;cin>>n>>m>>p;
    
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%p;
        }
    }
        
    int ans=0;
    for(int x=1;x<=n;x++){
        int tmp=0;
        
        int a1=(qpow(2,x,p)-1+p)%p;
        a1=qpow(a1,m-1,p);
        
        int a2=qpow(2,m-1,p);
        a2=qpow(a2,n-x,p);
        
        int a3=f[n][x];
        tmp=a1*a2%p*a3%p;
        
        ans=(ans+tmp)%p;
    }
    cout<<ans<<"\n";
}

 

B

A的plus版，但也不难。多了一个限制是：能选出2个不同的子序列使得其AND和为1。

2个不同的情况很多种不好计算，反向考虑什么时候选不出来？当且仅当每个末尾为1的数都要选。

问题化简成有n个数要覆盖m个位，每个数都至少有一个自己唯一覆盖的位置。

dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])*i

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
#define int long long
int f[N][N],n,m,p;
int qpow(ll a,int b){
    a%=p;
    ll ret=1;
    while(b){
        //TODO
        if(b&1) ret=ret*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ret;
}
int dp[N][N];
signed main(){
    cin>>n>>m>>p;
    f[0][0]=1;
    for(int i=1;i<=5002;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%p;
        }
    }
    
    ll ans=0;
    for(int x=1;x<=n;x++){
        ll a1=(qpow(2,x)-1+p)%p;a1=qpow(a1,m-1);
        int a2=qpow(2,m-1);a2=qpow(a2,n-x);
        int a3=f[n][x];
        ans=(ans+a1*a2%p*a3%p)%p;
    }
//    cout<<"ans: "<<ans<<"\n";
    
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=m;j++){
            dp[i][j]=1ll*((dp[i-1][j-1]+dp[i][j-1])%p)*i%p;
            //  cout<<i<<" "<<j<<" :"<<dp[i][j]<<"\n";
        }
    }
    
    ll tot=0;
    for(int k=2;k<=n;k++){
        int x=qpow(2,(m-1)*(n-k));
        int y=(qpow(2,k)-k-1+p)%p;
        ll tmp=1;
        for(int t=m-1;t>=k;t--){
            tot+=tmp*f[m-1][t]%p*dp[k][t]%p*f[n][k]%p*x%p;
            //    cout<<k<<" "<<t<<" : "<<f[m-1][t]*dp[k][t]%p*f[n][k]%p*qpow(2,(m-1)*(n-k)%p)%p*qpow((qpow(2,k)-k-1+p)%p,m-1-t)<<"\n";
            tot%=p;
            tmp=tmp*y%p;
        }
    }
    tot+=(ll)qpow(2,(m-1)*(n-1))*n%p;
    tot%=p;
    ans=(ans-tot+p)%p;
    cout<<ans<<"\n";
}

C

签到

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=1e9+7;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int q;
    cin>>q;
    int sum=0;// a1+a2+a3
    int tot=0;// s1+s2+s3
    int len=0;
    vector<int>a;
    while(q--){
        int t,v;
        cin>>t>>v;
        for(int i=1;i<=t;i++){
            sum=(sum-a.back()+mod)%mod;
            tot=(tot-a.back()*len%mod+mod)%mod;
            len--;
            a.pop_back();
        }
        a.push_back(v);
    //    cout<<tot<<" "<<len<<" "<<sum<<"\n";
        tot+=(len*v%mod+v)%mod;
        tot%=mod;
        len++;
        sum+=v;
        sum%=mod;
        cout<<tot<<"\n";
    }
}

D

没场切，当队友说出这个模数很小，先算出答案后再取模而我没有反对意见时，这道题就已经完蛋了。。

切入点在于模数，没有很大，且是2^21，启发我们在位运算上做文章。

显然先拆位，设当前在第 k 位，拆完后询问转化为有多少后缀和在第 k 位上为1。

后缀和不好处理，如果直接从后缀和入手，每次操作对整个数列都会产生影响。

考虑转化成前缀和，则后缀和 s[i]=sum[n]-sum[i-1]，求有多少个 s[i] 在第k位上为1。

这里直接算肯定也不行，”在第k位上为1“可以转化成模意义下的加法运算：(sum[n]-sum[i-1]) % (2^(k+1)) >= 2^k

令x=-sum[i-1] % (2^(k+1))   =>  (sum[n]+x)  % (2^(k+1)) >= 2^k

 又 (sum[n]+x)  % (2^(k+1)) <= 2^(k+1) 所以  2^(k+1) >= (sum[n]+x)  % (2^(k+1)) >= 2^k 每次询问相当于固定sum[n]，求有多少x满足条件。满足条件的x是一段(或者两段连续的值) R = 2^(k+1)-sum[n]  >= x >= 2^k -sum[n] = L 若 L <= R，直接询问[L,R]有多少个数即可，用权值树状数组维护 若 R<L ,说明在mod意义下R溢出了，跑到了前面去，就是两段：[0,R]  和  [L，2^(k+1)-1] 
#include<bits/stdc++.h>
using namespace std;
const int N = 2097152+5; 
int lowbit(int x) {
	return x&(-x);
}
struct ft{
	int a[N],n;
	void init(int len){
		n=len;
		for(int i=1;i<=n;i++) a[i]=0;
	}
	void add(int pos,int v){
		pos++;
		for(int i=pos;i<=n;i+=lowbit(i))
			a[i]+=v;
	}
	int sum(int pos){
		if(pos<0) return 0;
		pos++;
		int ret=0;
//		cout<<pos<<" LEN: "<<n<<endl;
		for(int i=pos;i;i-=lowbit(i))
			ret+=a[i];
		return ret;
	}
	int query(int l,int r){
		if(l>r) return 0;
		return sum(r)-sum(l-1);
	}
}BIT[21];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	for(int i=0;i<=20;i++) BIT[i].init((1<<(i+1)));
	vector<int>a;
	int q;cin>>q;
	
	int sum=0;
	for(int k=0;k<=20;k++){
		int tot,p=1<<(k+1);
		tot=(p-sum%p)%p;
		BIT[k].add(tot,-1);
	}
	
	
	while(q--){
		//TODO
		int t,v;cin>>t>>v;
		for(int j=1;j<=t;j++){
			int x=a.back();
			for(int k=0;k<=20;k++){
				int tot,p=1<<(k+1);
				tot=(p-sum%p)%p;
				BIT[k].add(tot,-1);
			}
			sum-=x;
			a.pop_back();
		}

		sum+=v;
		a.push_back(v);
		for(int k=0;k<=20;k++){
			int tot,p=1<<(k+1);   
			tot=(p-sum%p)%p;
		//	cout<<k<<" add "<<tot<<"\n";
			BIT[k].add(tot,1);
		}
		
		int ans=0;
		for(int k=0;k<=20;k++){
			int p=1<<(k+1),p1=1<<k;
			int l=(p1-sum%p+p)%p,r=(p-1-sum%p+p)%p,cnt=0;
		//	cout<<"["<<l<<","<<r<<"]"<<"\n";
		//	cout<<BIT[k].query(l,r)<<" "<<BIT[k].query(0,r)<<" "<<BIT[k].query(l,p-1)<<"\n";
			if(l<=r) cnt=BIT[k].query(l,r);
			else cnt=cnt+BIT[k].query(0,r)+BIT[k].query(l,p-1);
			if(cnt&1) {
			//	cout<<l<<" "<<r<<"\n";
				ans|=(1<<k);
			}
		}
		cout<<ans<<"\n";
	}
}

标签：return,int,sum,多校,ret,cin,2024,牛客,long
From： https://www.cnblogs.com/liyishui2003/p/18309078

相关文章

  • 2024 暑假集训杂题选做
    目录写在前面CF1981DCF1992F写在最后写在前面我是飞物。CF1981D2400妈的好诡异的题场上拿到这题我都不知道我要干啥呃呃考虑到每个合数均为若干质数的乘积，则若构造方案中有合数，可以将合数替换为质数从而减少使用的权值的种类数，于是仅需考虑使用质数构造，则此时并不需要考虑具......
  • 牛客day1的补题和总结
    C和I是签到题，没什么好说的。从A开始。A读题读了我20分钟，我才把样例弄懂。。这题目比cf阴间一佰倍，主要也是这类题的题面就是麻烦，有时候中文的题面的也能让我写一半回去再读几遍。这个主要就是写太慢了。完全可以更快的，而且这个思路我觉得大部分其实是lhgg帮我出的，我自己的思路......
  • 2024PHP在线客服系统源码+完全开源 带详细搭建教程
    本文是一个在线客服聊天系统源码。这是一款2024最新版本的PHP客服源码。基于ThinkPHP8.0+workerman，整体架构新颖全新UI，PHP客服端以及界面等即时通讯websocket服务端需要命令行执行。源码下载在下面链接中，下载zip压缩包https://gitee.com/source-code-home/php-customer-se......
  • 2024-07-18 浅尝rollup-plugin-visualizer——文件打包分析体积大小
    前言：vite+vue项目rollup-plugin-visualizer：一个用于Rollup构建系统的插件，它能够生成可视化的报告，展示你的项目构建后的模块依赖关系和文件大小。仓库：https://github.com/btd/rollup-plugin-visualizer安装：yarnaddrollup-plugin-visualizer配置（vite.config.ts）：import{......
  • Java开发新趋势！MyEclipse v2024.1全新首发——支持AI编码协助
    在MyEclipse 2024中，通过Copilot集成提供的AI编码协助，让开发者的生产力提高了近10倍；同时支持Java22，并部署到最新版本的应用服务器(如WildFly和Payara)；拥有更高性能的Spring工具支持更流畅的编码体验，而语言服务器更新确保对所有现代web技术的最新语言支持。MyEclipse的现有用户可......
  • 2024-07-18 闲话 两周年后的某一天
    soytony在群里问啥时候有yspm闲话两周年，我想说让APJ用Day1分数和我交换这篇闲话，但是这种行为也太过于没有素质了，于是我先写一波，当成他考完Day1能看到的依托答辩吧。昨天晚上回家了，所以主题可以是回家？幼儿园小学初中每天上完学就回家，在家里也就是吃饭，睡觉，有时候写作业，家......
  • 河南萌新联赛2024第（一）场：河南农业大学
    1.D-小蓝的二进制询问原题链接：https://ac.nowcoder.com/acm/contest/86639/D我们列举一些二进制数，发现在第一位永远是01的循环，第二位是0011的循环。。。第n位也是如此，所以可以得出每位上的循环节是2k,且前一半的数都是0。每次在计算某数时的1的总个数可以计算他是循环节的......
  • 20240718二分图
    一.基础概念1.定义：如果一个图的所有顶点可以被分成两个集合U和V，使得每条边连接的两个顶点都分别属于两个不同的集合，那么这个图就是一个二分图（BipartiteGraph）。2.性质：每个偶环都是二分图如果一个二分图中存在奇环，则它不是二分图。二.霍尔定理前言：在hloj上有这个内容，不知......
  • 河南萌新联赛2024第（一）场 补题报告
    小蓝的二进制询问找规律，可以发现把从0开始的十进制数字转化为二进制。每一个二进制位有0或1两种状态。从低到高的第一位以2为周期，第二位以4为周期，第三位以8为周期……也就是说第n位以2^{n}为周期。每个周期都是前一半是0，后一半是1。举例：000001010011100……#inclu......
  • 2024.7.17
    springboothivejdk17更换成了jdk1.8pom.xml测试配置和hive连接的依赖<dependency><groupId>org.junit.vintage</groupId><artifactId>junit-vintage-engine</artifactId><version>5.7.2</......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99