結果
| 問題 | No.1025 Modular Equation |
| ユーザー |
 noimi
|
| 提出日時 | 2020-04-10 23:23:13 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,771 ms / 5,000 ms |
| コード長 | 6,754 bytes |
| コンパイル時間 | 2,265 ms |
| コンパイル使用メモリ | 187,596 KB |
| 実行使用メモリ | 31,408 KB |
| 最終ジャッジ日時 | 2024-09-16 01:04:30 |
| 合計ジャッジ時間 | 47,060 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 60 ms
29,148 KB |
| testcase_01 | AC | 61 ms
29,084 KB |
| testcase_02 | AC | 61 ms
29,404 KB |
| testcase_03 | AC | 68 ms
29,156 KB |
| testcase_04 | AC | 62 ms
29,160 KB |
| testcase_05 | AC | 61 ms
29,152 KB |
| testcase_06 | AC | 64 ms
29,284 KB |
| testcase_07 | AC | 67 ms
29,028 KB |
| testcase_08 | AC | 64 ms
29,280 KB |
| testcase_09 | AC | 2,494 ms
30,056 KB |
| testcase_10 | AC | 2,580 ms
30,188 KB |
| testcase_11 | AC | 1,927 ms
29,796 KB |
| testcase_12 | AC | 1,844 ms
29,720 KB |
| testcase_13 | AC | 1,573 ms
29,796 KB |
| testcase_14 | AC | 1,582 ms
29,668 KB |
| testcase_15 | AC | 1,358 ms
29,668 KB |
| testcase_16 | AC | 1,303 ms
29,540 KB |
| testcase_17 | AC | 1,343 ms
29,476 KB |
| testcase_18 | AC | 1,269 ms
29,668 KB |
| testcase_19 | AC | 1,508 ms
30,436 KB |
| testcase_20 | AC | 1,451 ms
30,056 KB |
| testcase_21 | AC | 1,497 ms
29,924 KB |
| testcase_22 | AC | 1,489 ms
29,924 KB |
| testcase_23 | AC | 1,869 ms
31,208 KB |
| testcase_24 | AC | 2,771 ms
30,188 KB |
| testcase_25 | AC | 2,097 ms
29,924 KB |
| testcase_26 | AC | 1,877 ms
29,728 KB |
| testcase_27 | AC | 1,427 ms
29,540 KB |
| testcase_28 | AC | 1,406 ms
29,672 KB |
| testcase_29 | AC | 1,450 ms
29,540 KB |
| testcase_30 | AC | 1,599 ms
30,304 KB |
| testcase_31 | AC | 1,654 ms
30,560 KB |
| testcase_32 | AC | 1,987 ms
31,408 KB |
| testcase_33 | AC | 62 ms
29,184 KB |
| testcase_34 | AC | 1,201 ms
29,540 KB |
コンパイルメッセージ
main.cpp: In function 'int primitive_root(long long int)':
main.cpp:176:1: warning: control reaches end of non-void function [-Wreturn-type]
176 | }
| ^
ソースコード
#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vecpll vector<pll>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vecll>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),(x)))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),(x)))
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
string stin() {string s;cin>>s;return s;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
vec iota(int n){vec a(n);iota(all(a),0);return a;}
void print(){putchar(' ');}
void print(bool a){cout<<a;}
void print(int a){cout<<a;}
void print(long long a){cout<<a;}
void print(char a){cout<<a;}
void print(string &a){cout<<a;}
void print(double a){cout<<a;}
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } cout<<endl;}
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ cout<<" "; print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ cout<<'(';print(p.first); cout<<","; print(p.second);cout<<')'; }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ cout<<" "; print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
#define _GLIBCXX_DEBU
#define endl '\n'
#ifdef _MY_DEBUG
#undef endl
#define debug(x) cout<<#x<<": "<<x<<endl
void err(){}
template<class T> void err(const T& t){ print(t); cout<<" ";}
template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }
#else
#define debug(x)
template<class... T> void err(const T&...){}
#endif
#pragma endregion
const ll MOD=1e9+7;
const int N=1100000;
template <ll Modulus> class modint {
using u64 = ll;
public:
u64 a;
constexpr modint(const u64 x = 0) noexcept : a(((x % Modulus) + Modulus)%Modulus) {}
constexpr u64 &value() noexcept { return a; }
constexpr const u64 &value() const noexcept { return a; }
constexpr modint operator+(const modint rhs) const noexcept {
return modint(*this) += rhs;
}
constexpr modint operator-(const modint rhs) const noexcept {
return modint(*this) -= rhs;
}
constexpr modint operator*(const modint rhs) const noexcept {
return modint(*this) *= rhs;
}
constexpr modint operator/(const modint rhs) const noexcept {
return modint(*this) /= rhs;
}
constexpr modint &operator+=(const modint rhs) noexcept {
a += rhs.a;
if (a >= Modulus) {
a -= Modulus;
}
return *this;
}
constexpr modint &operator-=(const modint rhs) noexcept {
if (a < rhs.a) {
a += Modulus;
}
a -= rhs.a;
return *this;
}
constexpr modint &operator*=(const modint rhs) noexcept {
a = a * rhs.a % Modulus;
return *this;
}
constexpr modint &operator/=(modint rhs) noexcept {
u64 exp = Modulus - 2;
while (exp) {
if (exp % 2) {
*this *= rhs;
}
rhs *= rhs;
exp /= 2;
}
return *this;
}
};
#define mint modint<MOD>
mint inv[N],comb[N],prd[N],invprd[N];
void calc_inv(){
inv[1]=1;
rep2(i,2,N-1){
inv[i]=inv[MOD%i]*(-MOD/i);
}
return;
}
void calc_product(){
prd[0]=prd[1]=1;
invprd[0]=invprd[1]=1;
rep2(i,2,N-1){
prd[i]=prd[i-1]*i;
invprd[i]=inv[i]*invprd[i-1];
}
return ;
}
mint cmb(int a,int b){
if(a<b)return 0;
if(a<0||b<0)return 0;
return {prd[a]*invprd[b]*invprd[a-b]};
}
mint modpow(mint x,ll n){
if(n==0) return 1;
mint res=modpow(x*x,n/2);
if(n&1) res=res*x;
return res;
}
void calc(){calc_inv();calc_product();}
using vmint = vector<mint> ;
ostream& operator<<(ostream& os, mint a){
os << a.a ;
return os;
}
int primitive_root(ll mod){
if(mod==2)return 1;
vec used(110000);
rep2(i,2,mod){
ll now=1;
if(used[i])continue;
rep(j,mod-2){
now=(now*i)%mod;
used[now]=1;
if(now==1)break;
if(j==mod-3)return i;
}
}
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);
int p=in(),n=in(),k=in(),b=in();
vec a;rep(i,n)a.pb(in());
ll d = gcd(p-1,k);
ll g = primitive_root(p);
vec c{0,1};
rep(i,d-1){
c.pb(c.back()*g%p);
}
vmint dp(d+1);
ll G = g; // g^k
rep(i,k-1)G = G*g%p;
vecll t{G};
rep(i,(p-1)/d-1){
t.pb(t.back()*G%p);
}
int S = (p-1)/d;
// gの何乗か
vec iv(p);
ll tmp=1;
iv[0]=-1;
rep(i,p-1){
iv[tmp]=i;
tmp=tmp*g%p;
}
dp[0]=1;
calc();
rep(i,n){
vmint next(d+1);
rep(j,d+1){
for(auto e:t){
ll A = iv[(c[j]+a[i]*e)%p];
if(A==-1){
next[0]+=dp[j]*d;
}
else {
A%=d;
next[A+1]+=dp[j]*d;
}
}
}
rep(j,d+1)dp[j]+=next[j];
}
if(b==0){
cout<<dp[0]<<endl;
}
else
cout << dp[iv[b]%d+1]*inv[S] << endl;
}