題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)長(zhǎng)度為 n 的數(shù)列，現(xiàn)在問(wèn)能否選出一個(gè)子序列，滿足其累加之和可以整除 m

題目分析：可以當(dāng)做背包去思考，$d{p}_{i,j}$代表的是選了前 i 個(gè)數(shù)后是否可以組合出累加之和對(duì) m 取余等于 j 的數(shù)，那么答案顯然就是看一下 $d{p}_{n,m}$ 是否為 1 即可

不過(guò)時(shí)空復(fù)雜度都是 n * m 級(jí)別的，因?yàn)槭?01 背包，所以可以將空間復(fù)雜度優(yōu)化掉一維，到此為止分支出了兩種做法：

因?yàn)?dp 數(shù)組只有 0 或 1 兩種狀態(tài)，所以不難想到可以用 bitset 進(jìn)行優(yōu)化，用 bitset 優(yōu)化后時(shí)間復(fù)雜度除以 64，就在可行范圍內(nèi)了

還有一種做法需要一點(diǎn)思維，假設(shè)現(xiàn)在有 n 個(gè)數(shù)，如果 n > m 的話，那么對(duì) n 個(gè)數(shù)維護(hù)一個(gè)前綴和，根據(jù)鴿巢原理可知，一定會(huì)有兩個(gè)位置是相等的（因?yàn)榍熬Y和都需要對(duì) m 取余），比較顯然的就是這兩個(gè)位置之間的數(shù)求和是可以整除 m 的，所以當(dāng) n 大于 m 時(shí)直接輸出 yes 即可，這樣再去 dp 的時(shí)間復(fù)雜度就下降到了 m * m

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int a[N];bitset<2020>dp,temp;int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]%=m;if(a[i]==0)return 0*puts("YES");}if(n>m)return 0*puts("YES");dp[0]=1;for(int i=1;i<=n;i++){temp.set();temp<<=a[i];dp|=(dp<<a[i])&temp;dp|=(dp>>m);}puts(dp[m]?"YES":"NO");return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 577B Modulo Sum(dp+bitset优化)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。