-
Notifications
You must be signed in to change notification settings - Fork 0
/
10036.cpp
132 lines (124 loc) · 4.84 KB
/
10036.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**Bismillahir Rahmanir Rahim**/
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf 100000000
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repl(i,n) for(int i=1;i<=n;i++)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]={0,0,1,-1,1,-1,1,-1},dy[]={1,-1,0,0,1,-1,-1,1};
typedef long long ll;
typedef long l;
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
inline void cn( long &n )//fast input function
{
n=0;
long ch=getchar();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar();}
while(ch >= '0' && ch <= '9')
n = (n<<3)+(n<<1) + ch-'0', ch=getchar();
n=n*sign;
}
template<class T> void cmin(T &a,T b){if(b<a) a=b;}
template<class T> void cmax(T &a,T b){if(b>a) a=b;}
template<class T> int len(const T&c){return (int)c.size();}
template<class T> int len(char c[]){return (int)strlen(c);}
string itos(long n){string s;while(n){s+=(n%10+48);n/=10;}reverse(all(s));return s;}
long stoi(string s){long n=0;rep(i,len(s))n=n*10+(s[i]-48);return n;}
//Polya-Burnside theory : (n^6+3n^4+12n^3+8n^2)/24
#define DEBUG 1
#if DEBUG && !ONLINE_JUDGE
#define debug(args...) (Debugger()) , args
class Debugger { public: Debugger(const std::string& _separator = ", ") : first(true), separator(_separator){} template<typename ObjectType> Debugger& operator , (const ObjectType& v) { if(!first) std::cerr << separator; std::cerr << v; first = false; return *this; } ~Debugger() { std::cerr << endl;} private: bool first; std::string separator; }; template <typename T1, typename T2> inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; } template<typename T> inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v) { bool first = true; os << "["; for(unsigned int i = 0; i < v.size(); i++) { if(!first) os << ", "; os << v[i]; first = false; } return os << "]"; } template<typename T> inline std::ostream &operator << (std::ostream & os,const std::set<T>& v) { bool first = true; os << "["; for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) { if(!first) os << ", "; os << *ii; first = false; } return os << "]"; } template<typename T1, typename T2> inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v) { bool first = true; os << "["; for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii) { if(!first) os << ", "; os << *ii ; first = false; } return os << "]"; }
#else
#define debug(args...)
#endif
long n,k,ar[10005];
int dp[10005][105];
int rec(int i,long m)
{
if(i==n)
{
if((m%k)==0)
return 1;
return 0;
}
if(i>=n) return 0;
if(dp[i][m]!=-1) return dp[i][m];
int r1,r2;
r1=rec(i+1,(ar[i]+m)%k);
if(((m-ar[i])%k)<0)
r2=rec(i+1,((m-ar[i])%k)+k);
else
r2=rec(i+1,((m-ar[i])%k));
return dp[i][m]=(r1|r2);
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
long t,kk;
cin>>t;
for(kk=1;kk<=t;kk++)
{
mem(dp,-1);
cin>>n>>k;
rep(i,n) cin>>ar[i];
if(rec(0,0))
cout<<"Divisible\n";
else cout<<"Not divisible\n";
}
return 0;
}