P8565 Sultan Rage题目描述有一个数列{an}\{a_n\}{an​}满足对nmn mnm均有an∑j1man−ja_n\sum\limits_{j1}^m a_{n-j}an​j1∑m​an−j​并且a1,a2,⋯ ,ama_1,a_2,\cdots,a_ma1​,a2​,⋯,am​是输入中给出的正整数。qqq次询问每一次给出一个正整数xxx问有多少个不可重正整数集SSS满足∑s∈Sasx\sum\limits_{s\in S}a_sxs∈S∑​as​x。答案对质数998244353998244353998244353取模。本题有多组数据。输入格式本题有多组数据。第一行一个整数TTT表示数据组数。对于每一组数据第一行两个整数m,qm,qm,q。第二行mmm个整数a1,a2,⋯ ,ama_1,a_2,\cdots,a_ma1​,a2​,⋯,am​。第三行qqq个整数每一个整数代表一次询问。输出格式对于每组询问输出一行表示答案。输入输出样例 #1输入 #12 2 5 1 1 3 5 7 9 11 3 5 1 2 5 4 7 10 18 22输出 #13 3 3 5 5 0 1 1 1 1说明/提示对于所有数据T5T5T52≤m≤1002 \le m \le 1002≤m≤1001≤q,ai≤1001 \le q,a_i \le 1001≤q,ai​≤1001≤x≤10181 \le x \le 10^{18}1≤x≤1018。测试点编号m≤q≤ai≤x≤特殊性质1∼28881003∼51515103617∼111A12∼16217∼20 \def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c}\hline \textbf{测试点编号}\bm{m\le}\bm{q \le }\bm{a_i \le } \bm{x \le}\bm{\textbf{特殊性质}}\cr\hline \textsf1\sim \sf2 88 8 100\cr\hline \sf3\sim 5 15 1510^3 \cr\hline \textsf6 1 \cr\hline \sf7\sim 11 1 \textsf{A}\cr\hline \sf12\sim 16 2 \cr\hline \sf17\sim 20 \cr\hline \end{array}测试点编号1∼23∼567∼1112∼1617∼20​m≤8152​q≤81​ai​≤815​x≤1001031​特殊性质A​​A\textsf AAm10m10m10且xxx在所有可能的xxx中随机生成。C实现#includebits/stdc.husingnamespacestd;usinglllonglong;usingpiipairint,int;llread(){ll ret0,sgn0;charchgetchar();while(!isdigit(ch))sgn|ch-,chgetchar();while(isdigit(ch))retret*10ch-0,chgetchar();returnsgn?-ret:ret;}constintN180,mod998244353;constll INF1e18;intn,q;ll a[N],sum[N];mapll,intmp[N];intdfs(ll x,intcur){if(x0||xsum[cur])return0;if(!cur)return(x0);if(mp[cur].count(x))returnmp[cur][x];returnmp[cur][x](dfs(x-a[cur],cur-1)dfs(x,cur-1))%mod;}intmain(){intTread();while(T--){nread(),qread();for(inti1;in;i)a[i]read();intmn;while(a[m]INF){a[m]0;for(inti1;in;i)a[m]a[m-i];}nm-1;for(inti1;in;i){sum[i]sum[i-1]a[i];mp[i].clear();}while(q--){ll xread();printf(%d\n,dfs(x,n));}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容