网页欣赏网站,需要做网站的行业,怎样查找网站域名,网站蜘蛛抓取正题 题目大意
定义函数f(x)(xf(x)(xf(x)(x为一个序列))) 若任意一个xi1x_i1xi1那么有f(x)1f(x)1f(x)1 若有一个xi0x_i0xi0那么有f(x)0f(x)0f(x)0 其他的#xff0c;有f(x)(∑j1nf(x1...,xj−1,...xn))%2f(x)(\sum_{j1}^nf(x_{1}...,x_j-1,...x_n))\% 2f(x)(j1∑nf(x1…正题 题目大意
定义函数f(x)(xf(x)(xf(x)(x为一个序列))) 若任意一个xi1x_i1xi1那么有f(x)1f(x)1f(x)1 若有一个xi0x_i0xi0那么有f(x)0f(x)0f(x)0 其他的有f(x)(∑j1nf(x1...,xj−1,...xn))%2f(x)(\sum_{j1}^nf(x_{1}...,x_j-1,...x_n))\% 2f(x)(j1∑nf(x1...,xj−1,...xn))%2 给出li,ril_i,r_ili,ri求∑li≤xi≤rif(x)\sum_{l_i\leq x_i\leq r_i} f(x)li≤xi≤ri∑f(x) 解题思路
我们发现对于xxx有f(x)∏i1n−1C∑xjxif(x)\prod_{i1}^{n-1}C_{\sum x_j}^{x_i}f(x)∏i1n−1C∑xjxi 然后又有CnkC_{n}^kCnk为奇数仅当(nk)amp;kk(nk)\amp;kk(nk)kk 然后转换为f(x)1f(x)1f(x)1的充要条件就是对于任意的1≤i≠j≤n1\leq i\neq j\leq n1≤i̸j≤n有(xixj)amp;xixi(x_ix_j)\amp; x_ix_i(xixj)xixi证明 然后我们数位dpdpdp用fi,jf_{i,j}fi,j表示到第iii位时状态jjj中0表示没有到达上界111表示到达了上界。
对于lil_ili我们可以对nnn维进行容斥即可。
时间复杂度O(50∗n∗(2n)2)O(50*n*(2^n)^2)O(50∗n∗(2n)2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N10,XJQ990804011;
ll T,n,l[N],r[N],x[N],f[60][1N],ans,MS;
ll solve(ll S)
{for(ll i0;in;i){x[i]((Si)1)?(l[i]-1):r[i];if(x[i]0) return 0;}memset(f,0,sizeof(f));f[51][0]1;for(ll i50;i0;i--){for(ll j0;jMS;j){if(!f[i1][j]) continue;ll now0;for(ll k0;kn;k)now|(1k)*(x[k]i1);(f[i][j|now](__builtin_popcount(j)1)*f[i1][j]XJQ)%XJQ;for(ll k0;kn;k)if((now(~j))k1)(f[i][j|(now^(1k))]f[i1][j]XJQ)%XJQ;}}ll ans0;for(ll i0;iMS;i)(ansf[0][i]XJQ)%XJQ;return ans;
}
int main()
{freopen(c.in,r,stdin);freopen(c.out,w,stdout);scanf(%lld,T);while(T--){scanf(%lld,n);MS1n;ans0;for(ll i0;in;i)scanf(%lld%lld,l[i],r[i]),l[i]--,r[i]--;for(ll i0;iMS;i)(ans(__builtin_popcount(i)1?XJQ-solve(i):solve(i))XJQ)%XJQ;printf(%lld\n,ans);}
}
