首页 > 代码库 > BZOJ 4513: [Sdoi2016]储能表
BZOJ 4513: [Sdoi2016]储能表
Description
求\(\sum_{i=0}^{n-1}\sum_{i=0}^{n-1}max\{i\)^\(j-k,0\}\)
\(n,m\leqslant 10^{18},k\leqslant 10^9\)
Solution
数位DP。
我好弱啊qwq...
\(f[i][na][nb][nc]\)表示枚举到第\(i\)位，是否卡\(n\)上界，是否卡\(m\)上界，是否卡\(k\)下界。
枚举\(i\)这一位01，\(j\)这一位01，枚举上一个状态，判断一下合法，计算转移后的状态，统计。
最后答案就是\(f[0][0][0][0]\)，这样正好小于n,m和大于k。
Code
/************************************************************** Problem: 4513 User: BeiYu Language: C++ Result: Accepted Time:7048 ms Memory:1300 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 70; inline LL in(LL x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } LL T,n,m,k,p;LL pw[N],f[N][2][2][2],g[N][2][2][2];void Add(LL &x,LL y) { x=(x+y%p)%p; } int main() { for(T=in();T--;) { n=in(),m=in(),k=in(),p=in(); memset(f,0,sizeof(f)),memset(g,0,sizeof(g)); for(int i=0;i<N;i++) pw[i]=(1LL<<i)%p; g[63][1][1][1]=1; for(int i=62;~i;--i) { int a=(n>>i)&1,b=(m>>i)&1,c=(k>>i)&1; for(int xx=0;xx<2;xx++) for(int yy=0;yy<2;yy++) { int zz=xx^yy; for(int aa=0;aa<2;aa++) for(int bb=0;bb<2;bb++) for(int cc=0;cc<2;cc++) { if(aa && xx>a) continue; if(bb && yy>b) continue; if(cc && zz<c) continue; int na=aa?(xx==a):0,nb=bb?(yy==b):0,nc=cc?(zz==c):0; Add(f[i][na][nb][nc],f[i+1][aa][bb][cc]+((LL)zz-c+p)*pw[i]%p*g[i+1][aa][bb][cc]%p); Add(g[i][na][nb][nc],g[i+1][aa][bb][cc]); } } }printf("%lld\n",f[0][0][0][0]); }return 0;}
BZOJ 4513: [Sdoi2016]储能表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。