题解：P11571 「chaynOI R1 T4」橙红色的鱼

· · 题解

题目传送门

题目介绍

问有多少个二维数对，使它们异或后转换成二进制后一的个数等于 m，它们的和转换成二进制后一的个数等于 s，且这两个数都小于等于 r，第一个数大于等于第二个数。

思路

输入很简单，已经是二进制了，无需高精度除法。考虑枚举两个数的每一位，很明显是二进制下的。

考虑枚举顺序，由于有加法，所以要考虑进位，只能从低位到高位。

考虑数字大小的限制，因为有大小关系，所以第二个数的限制是有关第一个数大小的，第一个数限制是有关 r 的。考虑限制的转移，和高位到低位的一触发就不会返回不同，从低位到高位一旦有一次当位数字大于应该大于等于它的数，都会返回到有限制的状态。

我们继续思考数字大小限制的细节。由于高位可以弥补低位超过限制，所以我们不管哪一位枚举都是从一到零。最后我们只用判断只有两个数限制都不存在的时候才计入答案，因为小于等于，所以开始限制就不存在。

再考虑限制的转移，我们计题目要求大于等于它的数为目标数。如果当前位大于目标数的这一位，限制存在。 如果相等，限制和原来一样。如果小于，限制不存在。

细节

由于进位，所以即使已经超过了 r 的位数也可能对和中的一的个数产生贡献。

代码

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
string number;
int m,s,cnt,mod=998244353,dp[205][2][2][205][205][2];
int dfs(int pos,int limit1,int limit2,int sn1,int sn2,int jw){
    if(dp[pos][limit1][limit2][sn1][sn2][jw]!=-1) return dp[pos][limit1][limit2][sn1][sn2][jw];
    int l1,l2,add1,add2,jwn,sum=0;
    if(pos==cnt+1){
        if(jw==1) sn2++;
        if(sn1==m&&sn2==s&&limit1!=0&&limit2!=0) return 1;
        return 0;
    }
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            if(i!=j) add1=1;
            else add1=0;
            jwn=(i+j+jw)/2;
            if((i+j+jw)%2==1) add2=1;
            else add2=0;
            if(i>number[cnt-pos+1]) l1=0;
            else if(i==number[cnt-pos+1]) l1=limit1;
            else l1=1;
            if(j>i) l2=0;
            else if(j==i) l2=limit2;
            else l2=1;
            sum+=dfs(pos+1,l1,l2,sn1+add1,sn2+add2,jwn); 
            sum%=mod;
        }
    }
    return dp[pos][limit1][limit2][sn1][sn2][jw]=sum;
}
signed main()
{
    cin>>number;
    cnt=number.size();
    for(int i=cnt;i>=1;i--) number[i]=number[i-1];
    for(int i=cnt;i>=1;i--) number[i]-='0';
    cin>>m>>s; 
    memset(dp,-1,sizeof dp);
    cout<<dfs(1,1,1,0,0,0);
    return 0;
}

:::