結果
問題 |
No.1189 Sum is XOR
|
ユーザー |
![]() |
提出日時 | 2020-08-22 13:37:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 2,386 ms |
コンパイル使用メモリ | 199,880 KB |
最終ジャッジ日時 | 2025-01-13 07:48:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 2000000005 int main(){ int N,K; cin>>N>>K; vector<int> c(1024,0); for(int i=0;i<N;i++){ int t; cin>>t; c[t]++; } if(K>11){ cout<<0<<endl; return 0; } vector dp(1025,vector(1024,vector<int>(K+1,0))); dp[0][0][0] = 1; for(int i=0;i<1024;i++){ for(int j=0;j<1024;j++){ for(int k=0;k<=K;k++){ if(dp[i][j][k]==0)continue; dp[i+1][j][k] = mod(dp[i][j][k]+dp[i+1][j][k]); if(k==K)continue; if(j&i)continue; dp[i+1][j^i][k+1] = mod(dp[i+1][j^i][k+1] + mod(dp[i][j][k]*c[i])); } } } int ans = 0; for(int i=0;i<1024;i++){ ans = mod(ans + dp.back()[i][K]); } cout<<ans<<endl; return 0; }