notes：题目还没有放在题库里 所有链接都是比赛里的

重复重复重复...重复重复（数学）

思路

1. 数字构成 ：$x$由相同数字 $d$ 重复 $k$ 次组成，可以表示为 $d×(10^k-1)/9$ 。

2. 倍数条件 ：$x$必须能被M整除，即 $d×(10^k -1)/9\%m=0$ 。

3. 优化搜索：对于每个可能的长度 $k$ （从 $n$ 向下到 $1$ ），检查是否存在数字 $d$ （从 $9$ 向下到 $1$ ）使得 $d×(10^k -1)/9$ 能被 $m$ 整除。

代码

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

int solve(int d,int k){
	int num=0;
	for(int i=0;i<k;i++){
		num=num*10+d;
	}
	return num;
}

signed main(){
	freopen("repeat.in","r",stdin);
	freopen("repeat.out","w",stdout);
    int n,m;
    cin >>n>>m;
    for(int d=9;d>=1;d--){
    	for(int k=n;k>=1;k--){
    		if(solve(d,k)%m==0){
    			for(int i=1;i<=k;i++){
    				cout <<d;
				}
				return 0;
			}
		}
	}
    return 0;
}

简单dp（01背包）

思路

如何求出最终答案

1. 问题转化

题目要求计算所有非空子集 $T$ 的 $f(T)$之和，其中 $f(T)$ 是 $T$ 的子集中和等于 $S$ 的数量。我们可以转化为：

• 对于所有和等于 $S$ 的子集 $U$，计算它在多少个父集 $T$ 中出现，然后求和。

2. 关键观察

• 如果 $U$ 是一个大小为 $k$ 的子集，且和为 $S$ ，那么包含 $U$ 的父集 $T$ 有 $2^{N-k}$ 个（因为剩下的 $N-k$ 个元素可选可不选）。
• 因此，每个这样的 $U$ 对答案的贡献就是 $2^{N-k}$ 。

3. 动态规划定义

定义 dp[j] 表示：所有能组成和 j 的子集的贡献总和（模 998244353）。这里的贡献就是每个子集 $U$ 对应的 $2^{N-|U|}$ 。

4. 动态规划转移

• 初始化：dp[0] = 2^N，表示空子集的贡献（虽然题目要求非空子集，但后续计算会自动处理）。
• 转移：
  • 对于每个数 a[i]，从 S 到 a[i] 逆向更新 dp：
    • dp[j] += dp[j - a[i]] * inv(2)，其中 inv(2) 是 2 的模逆元（即 499122177）。
  • 这里乘以 inv(2) 是因为：
    • 加入 a[i] 后，子集大小 k 增加 1，贡献从 $2^{N-k}$ 变为 $2^{N-(k+1)} = \frac{2^{N-k}}{2}$ 。
    • 由于模运算中不能直接除 $2$ ，所以乘以 $2$ 的逆元。

代码

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

const int tt=3e3+10,mod=998244353;
int a[tt],dp[tt];

int qmi(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans*=a;
			ans%=mod;
		}
		a*=a;
		a%=mod;
		b>>=1;
	}
	return ans;
}

signed main(){
	freopen("sample.in","r",stdin);
	freopen("sample.out","w",stdout);
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	dp[0]=qmi(2,n);
	for(int i=1;i<=n;i++){
		for(int j=m;j>=a[i];j--){
			dp[j]+=dp[j-a[i]]*qmi(2,mod-2);
			dp[j]%=mod;
		}
	}
	cout <<dp[m]%mod;
	return 0;
} 

谢谢