yukicoder : No.2062 Sum of Subset mod 999630629

横着解法。
https://yukicoder.me/problems/no/2062

問題

素数P=999630629を考える。
N要素の整数列Aが与えられる。
Aの部分列Sに対し、F(S)はSの和をPで割った剰余とする。

Aの全部分列に対し、F(S)の和を998244353で割った余りを求めよ。

解法

Aの全部分列の総和はsum(A)*(2^(N-1))。
sum(A)＜2*Pなので、Aの部分列のうち和がPを超えるものがX通りある場合、解はsum(A)*(2^(N-1))-P*Xとなる。

あとはXを数えよう。
sum(A)はPよりちょっと大きい程度。
なので、ナップサック問題の要領で、Sに選ばない要素の和がsum(A)-P以下に収まるケースを数え上げればよい。
EditorialではFPSを使っているが、愚直なDPでもなんとか間に合う。

ll N;
ll A[202020];
int C[505050];
const ll mo=998244353;
const ll P=999630629;
ll dp[505050];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll sum=0;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i];
		sum+=A[i];
		C[A[i]]++;
	}
	ret=sum*modpow(2,N-1)%mo;
	if(sum>=P) {
		unordered_map<ll,ll> dp;
		dp[sum-P]=1;
		sort(A,A+N);
		reverse(A,A+N);
		
		FOR(i,N) {
			vector<pair<ll,ll>> add;
			FORR2(a,b,dp) if(a>=A[i]) add.push_back({a-A[i],b});
			FORR2(a,b,add) dp[a]=(dp[a]+b)%mo;
		}
		FOR(j,sum-P+1) ret-=dp[j]*P%mo;
	}
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

横着してしまった…。