fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. //#define MOD 1000000007
  7. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  8. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  9. #define ALL(x) (x).begin(),(x).end()
  10. #define ii pair<int,int>
  11. #define iii pair<int,pair<int,int>>
  12. const int MOD = 998244353;
  13. const int MAXN = 5e5 + 7;
  14. int fact[MAXN],inv[MAXN],a[MAXN];
  15. int P(ll a,ll b){
  16.     if (b==1)return a;
  17.     ll res = P(a,b/2)%MOD;res = res*res%MOD;
  18.     if (b&1)return res*a%MOD;
  19.     return res;
  20. }
  21. ll C(int k,int n){
  22.     return fact[n]*inv[n-k]%MOD*inv[k]%MOD;
  23. }
  24. int main(){
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(0); cout.tie(0);
  27.     //freopen("cardscore.inp","r",stdin);
  28.     //freopen("cardscore.out","w",stdout);
  29.     fact[0] = 1;
  30.     FOR(i,1,MAXN - 1)fact[i] = fact[i-1]*i%MOD;
  31.     inv[MAXN - 1] = P(fact[MAXN - 1],MOD-2);
  32.     FOD(i,0,MAXN - 2)
  33.     inv[i] = inv[i+1]*(i+1)%MOD;
  34.     int tt;cin >> tt;
  35.     while(tt--){
  36.         int n = 26;
  37.         FOR(i,1,n)cin >> a[i];
  38.         ll s = 0;
  39.         FOR(i,1,n)s = s + a[i];
  40.         ll x = s / 2,y = s - s / 2;
  41.         vector<iii> v,tmp;
  42.         ll tot = 0;
  43.         FOR(i,1,n)tot = tot + a[i];
  44.         v.push_back({0,{0,1}});
  45.         FOR(i,1,20)if (a[i] > 0){
  46.             tmp.clear();
  47.             for (auto it : v){
  48.                 if (it.fi + tot >= x && it.fi + a[i] <= x)tmp.push_back({it.fi + a[i],{it.se.fi,it.se.se * C(a[i],x - it.fi) % MOD}});
  49.                 if (it.se.fi + tot >= x && it.se.fi + a[i] <= y)tmp.push_back({it.fi,{it.se.fi + a[i],it.se.se * C(a[i],y - it.se.fi) % MOD}});
  50.             }
  51.             tot = tot - a[i];
  52.             v.clear();
  53.             v = tmp;
  54.         }
  55.         ll ans = 0;
  56.         for (auto it : v)if (it.fi == x && it.se.fi == y)ans = (ans + it.se.se) % MOD;
  57.         cout << ans << '\n';
  58.     }
  59.     return 0^0;
  60. }/*
  61. 2 1 1
  62. 1 0 1
  63. 1 2 1
  64. */
Success #stdin #stdout 0.07s 38756KB
comments (?)
stdin
copy 
5
2 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 233527 233827
stdout
copy 
-209247082
0
0
560767064
0
https://ideone.com/ytz6tU
language:
C++ (gcc 8.3)
created:
1 day 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!