fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1'000'000'007;
  5.  
  6. long long modpow(long long a, long long e){
  7.     long long r = 1;
  8.     while(e){
  9.         if(e & 1) r = r * a % MOD;
  10.         a = a * a % MOD;
  11.         e >>= 1;
  12.     }
  13.     return r;
  14. }
  15.  
  16. int main() {
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.  
  20.     int N, K;
  21.     if(!(cin >> N >> K)) return 0;
  22.     vector<int> x(N);
  23.     for (int i = 0; i < N; ++i) cin >> x[i];
  24.  
  25.     // factorials up to K
  26.     vector<long long> fact(K+1), invfact(K+1);
  27.     fact[0] = 1;
  28.     for (int i = 1; i <= K; ++i) fact[i] = fact[i-1]*i % MOD;
  29.     invfact[K] = modpow(fact[K], MOD-2);
  30.     for (int i = K; i >= 1; --i) invfact[i-1] = invfact[i]*i % MOD;
  31.  
  32.     // DP convolution
  33.     vector<long long> dp(K+1, 0), ndp(K+1, 0);
  34.     dp[0] = 1;
  35.  
  36.     for (int i = 0; i < N; ++i) {
  37.         fill(ndp.begin(), ndp.end(), 0);
  38.  
  39.         // S_i[t]: số cách cho viên i dùng đúng t lượt (không tính đứng yên)
  40.         vector<long long> Si(K+1, 0);
  41.         for (int t = abs(x[i]); t <= K; ++t) {
  42.             if ( ((t - x[i]) & 1) == 0 ) { // t ≡ x_i (mod 2)
  43.                 int a = (t + x[i]) / 2;
  44.                 int b = (t - x[i]) / 2;
  45.                 if (a >= 0 && b >= 0)
  46.                     Si[t] = invfact[a] * invfact[b] % MOD;
  47.             }
  48.         }
  49.  
  50.         for (int s = 0; s <= K; ++s) if (dp[s]) {
  51.             for (int t = 0; s + t <= K; ++t) if (Si[t]) {
  52.                 ndp[s + t] = (ndp[s + t] + dp[s] * Si[t]) % MOD;
  53.             }
  54.         }
  55.         dp.swap(ndp);
  56.     }
  57.  
  58.     // Thêm lượt "đứng yên" và sắp xếp K lượt: nhân P(K, t) = K! / (K-t)!
  59.     long long ans = 0;
  60.     for (int t = 0; t <= K; ++t) {
  61.         if (dp[t] == 0) continue;
  62.         long long ways_place = fact[K] * invfact[K - t] % MOD;
  63.         ans = (ans + dp[t] * ways_place) % MOD;
  64.     }
  65.     cout << ans % MOD << '\n';
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
5 20
1 2 3 4 5
stdout
copy 
182783854
https://ideone.com/0gSSVG
language:
C++14 (gcc 8.3)
created:
11 days 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!