用五百丁做名字的简历网站,做网站什么商品好,新乡市网站建设公司,商品推销题意#xff1a;求iM的popcount的和#xff0c;i属于0……N
主要思路还是变加为乘。
举个例子N22#xff0c;即10110
假设M的第3位是1#xff0c;分析N中#xff1a;
00110
00111
00100
00101
发现其实等价于
0010
0011
0000
0001
也就是左边第4位和第5… 题意求iM的popcount的和i属于0……N
主要思路还是变加为乘。
举个例子N22即10110
假设M的第3位是1分析N中
00110
00111
00100
00101
发现其实等价于
0010
0011
0000
0001
也就是左边第4位和第5位不变右边第1位和第2位不变拼接起来相当于0000~0011
01110
01111
01100
01101
等价于
0110
0111
0100
0101
相当于0100~0111
10110
10111
10100
10101
相当于1000~1010
最后把3个部分合一起就是0000~1010
如果M的第3位是0比如说10010二进制其实等价于求01110这个二进制数
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int mod998244353;
ll ans,n,m;
int main(){cinnm;for(int i0;i60;i){if((mi)1){ll mask(1lli)-1;if((ni)1){ll tmp(n(i1)i)|(nmask);//左边拼接上右边ans(anstmp1)%mod;} else {ll t(n-(1lli))|mask;//先把n更新一下注意要把右边变成最大值ll tmp(t(i1)i)|(tmask);//同样处理ans(anstmp1)%mod;}}}coutans;
} 题意共n把钥匙m次测试至少k把钥匙才打开门问满足所有测试条件的真钥匙的组合种类
位元枚举用位元表示所有真钥匙的组合然后保存每个测试的钥匙状态满足所有测试就是答案组合
#include bits/stdc.h
using namespace std;
int keys[20];
char r[105];
int f(int x){int ct0;while(x){if(x1)ct;x1;}return ct;
}
int main(){int n,m,k;cinnmk;//n把钥匙m个测试至少k把钥匙才能打开门for(int i0;im;i){int c;cinc;while(c--){int a;cina;keys[i]|1(a-1);//把i测试用的钥匙存起来}cinr[i];//最终门的状态}int ans0;for(int s0;s(1n);s){//枚举所有正确钥匙的组合情况bool er0;for(int i0;im;i){//看看是否满足所有的测试用例if((f(keys[i]s)kr[i]!o)||(f(keys[i]s)kr[i]o)){er1;break;}}ans!er;}coutans;
} 不难发现10101010101010101010 10*1010101010101010101
就是10*(10^010^210^410^610^810^1010^1210^1410^1610^18) 进行等比求和
10*(10^20-1)/(10^2-1)
那么输入一个N我们计算出其长度len
就是N*(10^010^len10^len*210^len*3……10^len*n-1)
就是N*(10^len*n)/(10^len-1)
然后知识点a/b%moda*b^(mod-2)%mod
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int MOD998244353;
ll f(ll x,ll y){x%MOD;ll res1;while(y){if(y1)resres*x%MOD;y1;xx*x%MOD;}return res;
}
ll inv(ll x){return f(x,MOD-2);
}
int main(){ll n;cinn;int len(to_string(n)).size();coutn%MOD * (f(f(10,n),len)-1)%MOD * inv(f(10,len)-1)%MOD\n;
} 题意一共有n个店每个店有许多口味问能尝到所有口味至少要去多少家店
位元枚举用位元来表示所有店的组合并保存每个店提供的口味状态如果某个组合中可提供所有的口味就行
#include bits/stdc.h
using namespace std;
int d[10];
int main(){int n,m;cinnm;//n个店m种口味for(int i0;in;i){string s;cins;for(char c:s){d[i](d[i]1)(co);//保存第i个店卖的口味状态}}int an100;for(int i0;i(1n);i){//枚举所有的店的组合int now0,cnt0;for(int j0;jn;j){if((ij)1)now|d[j],cnt;//把组合中的每个店卖的东西都合并起来}if(now(1m)-1)anmin(an,cnt);//如果当好覆盖了所有口味那就更新一次答案}coutan;
}
