T3 统计区间

solution

枚举区间右端点，求有几个左端点满足 $s_r - s_{l-1} = k$

可以用 hash 或者 unordered_map 在枚举时标记前缀和，在标记之前统计左端点数即可

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;

int n , k , a[N] , s[N] , ans;
unordered_map<int , int> mp;

signed main(){
	freopen("tjqj.in" , "r" , stdin);
	freopen("tjqj.out" , "w" , stdout);
	
	cin >> n >> k;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		
		s[i] = s[i - 1] + a[i];
	}
	mp[0] ++;
	for(int i = 1 ; i <= n ; i ++){
		if(mp[s[i] - k] > 0) ans += mp[s[i] - k];
		mp[s[i]] ++;
	}
	cout << ans;
	return 0;
}

T6 我讨厌非整数

solution

观察数据范围，用 $O(n^4)$ 的 dp 求解

注意到题目只要求求平均值是整数的个数，所以我们可以设 $dp_{i,j,k}$ 表示从 $1$ ~ $i$ 取 $j$ 个数并且这 $j$ 个数的和 $\mod j = k$的所有选择可能的个数

显然，状态转移方程需要考虑取 $a_i$ 和不取 $a_i$ 两种情况：

(不取 $a_i$ )

(取 $a_i$)

最后注意转移顺序，要先枚举整体的个数，再枚举从 $1$ ~ $n$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int mod = 998244353;

int n , a[N] , dp[N][N][N] , ans;

int main(){
	freopen("hate.in" , "r" , stdin);
	freopen("hate.out" , "w" , stdout);
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	for(int k = 0 ; k <= n ; k ++){
		memset(dp , 0 , sizeof dp);
		dp[1][0][0] = 1;
		
		for(int i = 1 ; i <= n ; i ++){
			for(int j = 0 ; j <= k ; j ++){
				for(int l = 0 ; l < k ; l ++){
					if(!dp[i][j][l]) continue;
					
					dp[i + 1][j][l] = (dp[i + 1][j][l] + dp[i][j][l]) % mod;
					if(j < k){
						int nl = (l + a[i]) % k;
						dp[i + 1][j + 1][nl] = (dp[i + 1][j + 1][nl] + dp[i][j][l]) % mod;
					}
				}
			}
		}
		ans = (ans + dp[n + 1][k][0]) % mod;
	}
	cout << ans;
	return 0;
}