結果

問題 No.1763 Many Balls
ユーザー chineristAC
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0