結果
問題 | No.1763 Many Balls |
ユーザー |
|
提出日時 | 2021-11-20 15:05:58 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,832 bytes |
コンパイル時間 | 19,549 ms |
コンパイル使用メモリ | 252,900 KB |
最終ジャッジ日時 | 2025-01-25 21:45:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 WA * 6 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>#include <unordered_map>#include <atcoder/all>using namespace std;using namespace atcoder;//using mint = modint998244353;#define rep(i,n) for (int i=0;i<n;i+=1)#define rrep(i,n) for (int i=n-1;i>-1;i--)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<endl;}ll lpow(int n,int k,int m){ll res = 1;ll e = n;while (k){if (k&1){res *= e;res %= m;}e = e * e;e %= m;k >>= 1;}return res;}const int mod = 90001;const int r = 13;const int r_60 = lpow(r,1500,mod);int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);string N;int M;cin>>N>>M;vec<ll> exp = {1};int k;rep(i,M){vec<ll> exp_f(90001);cin>>k;vec<int> A(k);rep(j,k){cin>>A[j];}rep(bit,(1<<k)){int cnt = 0;int L = 1;rep(j,k){if ((bit>>j) & 1){cnt += 1;L = lcm(L,A[j]);}}if (cnt==0){continue;}ll inv = lpow(L,mod-2,mod);int a = lpow(r_60,60/L,mod);if (cnt&1){rep(j,L){exp_f[lpow(a,j,mod)] += inv;exp_f[lpow(a,j,mod)] %= mod;}}else{rep(j,L){exp_f[lpow(a,j,mod)] -= inv;if (exp_f[lpow(a,j,mod)] < 0){exp_f[lpow(a,j,mod)] += mod;}exp_f[lpow(a,j,mod)] %= mod;}}}exp = convolution_ll(exp,exp_f);for (int j=mod;j<exp.size();j++){exp[j%mod] += exp[j];exp[j%mod] %= mod;}exp.resize(mod);for (int j=0;j<mod;j++){exp[j] %= mod;}}int residu = 0;rep(i,N.size()){int a = N[i]-'0';residu = 10 * residu + a;residu %= 90000;}ll res = 0;for (int a=0;a<mod;a++){res += exp[a] * lpow(a+1,residu,mod);res %= mod;}cout<<res<<endl;}