fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. int dp[3010][3010];
  7. int n,m;
  8. ll pre[3010];
  9. ll a[3010];
  10. ll b[3010];
  11. int MOD = 1000000007;
  12. ll sum;
  13. bool ok = true;
  14.  
  15. void sub1() {
  16.     dp[0][0] = 1;
  17.     for(int j = 1; j <= m; j++){
  18.         for(int i = j; i <= n; i++){
  19.             for(int k = j - 1; k < i; k++){
  20.                 sum = pre[i] - pre[k];
  21.                 if(sum % b[j] == 0){
  22.                     dp[i][j] += dp[k][j-1];
  23.                     if(dp[i][j] >= MOD)
  24.                         dp[i][j] -= MOD;
  25.                 }
  26.             }
  27.         }
  28.     }
  29.     cout << dp[n][m];
  30. }
  31.  
  32. void sub2() {
  33.     dp[0][0] = 1;
  34.     for(int i = 1; i < n ; i++){
  35.         dp[i][0] = 1;
  36.         dp[i][i] = 1;
  37.         for(int j = 1; j < i; j++){
  38.             dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
  39.             if(dp[i][j] >= MOD){
  40.                 dp[i][j] -= MOD;
  41.             }
  42.         }
  43.     }
  44.     cout << dp[n-1][m-1];
  45. }
  46.  
  47. int main(){
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     freopen("DIVGROUP.INP","r",stdin);
  51.     freopen("DIVGROUP.OUT","w",stdout);
  52.     cin >> n >> m;
  53.     for(int i = 1; i <= n; i++){
  54.         cin >> a[i];
  55.         pre[i] += pre[i-1] + a[i];
  56.     }
  57.     for(int j = 1; j <= m; j++){
  58.         cin >> b[j];
  59.         if(b[j] != 1)
  60.             ok = false;
  61.     }
  62.     if(ok) sub2();
  63.     else sub1();
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gs5DbV
language:
C++ (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!