BZOJ5123: [Lydsy1712月赛]线段树的匹配 记忆化搜索

思路十分显然，但是结构体的写法要注意.   

定义重载运算符可以有效地减小代码量.  

因为一个小错误调了半天，自闭了. 

code: 

#include <map> 
#include <cstdio>   
#define mod 998244353 
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;  
typedef long long ll;  
struct data 
{
    ll x,y;   
    data() {} 
    data(ll a,ll b) { x=a,y=b; }    
    data operator+(const data &a) const {    
        return data(x+a.x,y*a.y%mod); 
    }    
    data operator*(const data &a) const 
    {    
        if(x>a.x) return *this; 
        if(x<a.x) return a;   
        return data(x,(y+a.y)%mod); 
    }
};     
struct node 
{
    data f,g;
    node() {}    
    node(data a,data b) { f=a,g=b; }                                       
};    
map<ll,node>dp;   
node dfs(ll n) 
{ 
    if(dp.find(n)!=dp.end()) return dp[n];              
    node L=dfs(n-(n>>1)),R=dfs(n>>1);               
    return dp[n]=node((L.g+R.f+data(1,1))*(L.f+R.g+data(1,1))*(L.g+R.g+data(1,2)),(L.g+R.f)*(L.f+R.f)*(L.f+R.g)*(L.g+R.g));        
}
int main() 
{   
    // setIO("input");
    dp[1]=node(data(-100,0),data(0,1));     
    ll n; 
    scanf("%lld",&n);   
    node tmp=dfs(n);   
    data ans=(tmp.f*tmp.g);  
    printf("%lld %lld
",ans.x,ans.y);   
    return 0; 
}