結果
| 問題 | No.1025 Modular Equation |
| ユーザー |
 noimi
|
| 提出日時 | 2020-04-10 23:17:19 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,654 bytes |
| コンパイル時間 | 2,424 ms |
| コンパイル使用メモリ | 187,592 KB |
| 実行使用メモリ | 31,464 KB |
| 最終ジャッジ日時 | 2024-09-16 00:40:14 |
| 合計ジャッジ時間 | 51,162 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 TLE * 1 -- * 1 |
コンパイルメッセージ
main.cpp: In function 'int primitive_root(long long int)':
main.cpp:172:1: warning: control reaches end of non-void function [-Wreturn-type]
172 | }
| ^
ソースコード
#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<<endlvoid 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 endregionconst 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){rep2(i,2,mod){ll now=1;rep(j,mod-2){now=(now*i)%mod;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^krep(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;}elsecout << dp[iv[b]%d+1]*inv[S] << endl;}