牛客练习赛93 B(等寒假再好好练题，俺要学英语)

题目

题意: 给定n个数，进行m轮相互独立的选择，每一轮在n个数中任意选择一个数ai。得分为每次选择的数的累加和 % k，k为模数。求m轮过后分值中包含7或者9的方案数之和。 n = 100,m = 50,k = 50.

思路: 数据范围很小，考虑dp. f[i][j]表示前i轮，体积为j的方案数。f[i][j] 可以从 f[i-1][j - a[t]]转移,t = 1到n，花O(n)时间枚举从哪个数转移. 时间复杂度: O(m * k * n) 我赛时写了一个 nmkn的，50005000，也过了。当时想的是只要我一个数 % k以后满足含7、9就行，每次获得的分数 < k，最多获得n * k，体积本来只用算k的，算成了n * k，幸好数据范围小。 对于这种要对状态取模的dp注意取模，数据范围就是给定的变量了。 pay attention

代码:

// Problem: 斗地主
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11183/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i