結果
問題 | No.16 累乗の加算 |
ユーザー |
![]() |
提出日時 | 2016-01-01 22:45:08 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,033 bytes |
コンパイル時間 | 933 ms |
コンパイル使用メモリ | 83,524 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 05:07:04 |
合計ジャッジ時間 | 1,500 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
ソースコード
#include <iostream>#include <vector>#include <list>#include <deque>#include <queue>#include <stack>#include <map>#include <algorithm>#include <cmath>using namespace std;#define FOR(x,y) for(int x = 0;x < y;x++)#define LLI long long int#define FORR(x,arr) for(auto& x:arr)#define ALL(a) (a.begin()),(a.end())template<int um> class UF {public:vector<int> _parent,_rank;UF(){_parent=_rank=vector<int>(um,0);for(int i=0;i<um;i++){_parent[i]=i;}}int Find(int x){if(_parent[x] == x){return x;}_parent[x] = Find(_parent[x]);return _parent[x];}int Union(int x,int y){int xRoot = Find(x);int yRoot = Find(y);if(_rank[xRoot]>_rank[yRoot]){_parent[xRoot] = yRoot;return yRoot;}if(_rank[xRoot]<_rank[yRoot]){_parent[yRoot] = xRoot;return xRoot;}if(xRoot != yRoot){_parent[yRoot] = xRoot;_rank[xRoot]++;return xRoot;}return xRoot;}};map<LLI,int> counts;const LLI mod = 1000003;LLI Build(LLI a, const vector<LLI> bits){LLI r = 1;int i = 0;while(a > 0){if((a & 1) ==1){r *= bits[i];r %= mod;}i++;a >>= 1;}return r;}int main() {int x, N;cin >> x >> N;FOR(i, N){LLI a;cin >> a;counts[a]++;}vector<LLI> bits;LLI k = x;bits.push_back(k);LLI c = 1;while(c <= 100000000){k = k * k;k %= mod;c *= 2;bits.push_back(k);}LLI result = 0;FORR(r, counts){LLI m = Build(r.first, bits);m *= r.second;m %= mod;result += m;result %= mod;}cout << result << endl;return 0;}