下载搭建网站软件,企业网站建设合同范本免费,建设工程施工合同的范本,一款app的开发成本正题
题目链接:https://www.luogu.com.cn/problem/U138404?contestId36493 题目大意 nnn个数字#xff0c;每次询问一个区间有多少个三对数或为xxx。 解题思路
首先显然这些数都不能有xxx没有的位数#xff0c;那么我们选择的数都得是被xxx包含的#xff0c;这些数的数量…正题
题目链接:https://www.luogu.com.cn/problem/U138404?contestId36493 题目大意
nnn个数字每次询问一个区间有多少个三对数或为xxx。 解题思路
首先显然这些数都不能有xxx没有的位数那么我们选择的数都得是被xxx包含的这些数的数量很容易求但是我们还要求每个111位都得有一个数是111。
那么考虑容斥如果一个xxx的子集yyy的一的个数是比xxx少kkk那么容斥系数就是(−1)k(-1)^k(−1)k。然后计算即可。
时间复杂度O(28n)O(2^8n)O(28n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,Q,a[N],f[N][256],g[256];
ll C3(ll x)
{return x*(x-1)*(x-2)/6;}
int main()
{scanf(%lld%lld,n,Q);for(ll i1;in;i)scanf(%lld,a[i]);for(ll j0;j256;j)for(ll i1;in;i)f[i][j]f[i-1][j]((a[i]|j)j);g[0]1;g[1]-1;for(ll i2;i256;i)g[i]g[i1]*g[i1];while(Q--){ll l,r,x,ans0;scanf(%lld%lld%lld,l,r,x);for(ll ix;i;i(i-1)x)ansg[x]*g[i]*C3(f[r][i]-f[l-1][i]);printf(%lld\n,ans);}
}
