bzoj 4513 에너지 저장표
5649 단어 --dp(동적 계획)---디지털 dp
∑x=0n−1∑y=0m−1min(x⊕y−k,0)(modp)
네, 문제면은 여기까지.
디지털 dp 한 번만 해주세요.
기억화는 검색할 때 사실 많은 분류 토론이 필요 없어요. 구체적으로 코드를 보세요.
#include
using namespace std;
#define LL long long
const int maxn = 70;
LL n[maxn],m[maxn],k[maxn];
LL p;
LL cnt[maxn][2][2][2],dp[maxn][2][2][2];
LL tw[maxn];
void biter(LL x,LL *s){
for(int i = 0;i2;
x /= 2;
}
}
LL dfsn(int pos,bool un,bool um,bool uk){
if(pos < 0) return 1;
LL & ncnt = cnt[pos][un][um][uk];
if(ncnt != -1)
return ncnt;
int nb = un ? n[pos] : 1;
int mb = um ? m[pos] : 1;
ncnt = 0;
for(int i = 0;i<=nb;i++){
for(int j=0;j<=mb;j++){
LL x = i ^ j;
if(!uk || x >= k[pos]){
ncnt += dfsn(pos-1,un && i==nb,um && j == mb,uk && x==k[pos]);
ncnt %= p;
}
}
}
return ncnt;
}
LL dfs(int pos,bool un,bool um,bool uk){
if(pos < 0) return 0;
LL & ndp = dp[pos][un][um][uk];
if(ndp != -1)
return ndp;
int nb = un ? n[pos] : 1;
int mb = um ? m[pos] : 1;
ndp = 0;
for(int i=0;i<=nb;i++){
for(int j=0;j<=mb;j++){
LL x = i ^ j;
if(!uk || x >= k[pos]){
LL mid = x;
mid *= dfsn(pos-1,un && i== nb,um && j == mb,uk && x==k[pos]);
(mid *= tw[pos]) %= p;
ndp += mid;
(ndp += dfs(pos-1,un && i== nb,um && j == mb,uk && x==k[pos])) %= p;
}
}
}
return ndp;
}
LL cal(LL N,LL M,LL K){
tw[0] = 1;
for(int i=1;i1] * 2 ) % p;
}
N--,M--;
biter(N,n);
biter(M,m);
biter(K,k);
memset(dp,-1,sizeof(dp));
memset(cnt,-1,sizeof(cnt));
LL tim = dfsn(maxn-1,true,true,true);
LL val = dfs(maxn-1,true,true,true);
K %= p;
tim *= K % p;
(val -= tim % p ) %= p;
val += p;
val %= p;
return val;
}
int main(){
int T;
LL N,M,K;
cin>>T;
while(T-- && cin>>N>>M>>K>>p){
cout<return 0;
}
사람이 약해서 dfs를 두 번 썼는데...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
X mod f(x) HDU - 4389(디지털 dp)Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10 9), how many integer x that mod f(x) equal to 0. In...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.