萌新刚学OI,0pts请求DEBUG
  • 板块CF1073E Segment Sum
  • 楼主Hisy
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/24 17:14
  • 上次更新2024/7/24 17:26:30
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/7/24 17:14
#include<bits/stdc++.h>
#define MAXN 22
#define MAXM 1024
#define MOD 998244353
using namespace std;
typedef long long ll;
int k;
pair<int,ll> dp[MAXN][2][2][MAXM];
inline ll clac(string S){
	ll ans=0;
	for(int i=0;i<MAXN;++i){
		for(int front=0;front<=1;++front){
			for(int limit=0;limit<=1;++limit){
				for(int bit=0;bit<MAXM;++bit){
					dp[i][front][limit][bit]=make_pair(0,0ll);
				}
			}
		}
	}
	dp[0][0][0][0].first=1;
	for(size_t i=0;i<S.size();++i){
		for(int front=0;front<=1;++front){
			for(int limit=0;limit<=1;++limit){
				for(int bit=0;bit<MAXM;++bit){
					if(dp[i][front][limit][bit].first){
						pair<int,ll> now=dp[i][front][limit][bit];
						int high=limit?9:S[i]-'0';
						for(int j=0;j<=high;++j){
							int sonbit=bit;
							if(front||j){
								sonbit|=(1<<j);
							}
							pair<int,ll> &nxt=dp[i+1][j||front][limit||(j<high)][sonbit];
							(nxt.first+=now.first)%=MOD;
							(nxt.second+=now.first*j+now.second*10ll)%=MOD;
						}
					}
				}
			}
		}
	}
	for(int front=0;front<=1;++front){
		for(int limit=0;limit<=1;++limit){
			for(int bit=0;bit<MAXM;++bit){
				if(__builtin_popcount(bit)<=k){
					(ans+=dp[S.size()-1][front][limit][bit].second)%=MOD;
				}
			}
		}
	}
	return ans;
}
int main(){
	ll l,r;
	scanf("%lld %lld",&l,&r);
	printf("%lld",((clac(to_string(r))-clac(to_string(l-1)))%MOD+MOD)%MOD);
	return 0;
}
2024/7/24 17:14
加载中...