結果
問題 | No.1847 Good Sequence |
ユーザー | fumofumofuni |
提出日時 | 2022-02-19 01:04:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,709 bytes |
コンパイル時間 | 2,303 ms |
コンパイル使用メモリ | 211,480 KB |
実行使用メモリ | 20,404 KB |
最終ジャッジ日時 | 2024-06-29 10:08:57 |
合計ジャッジ時間 | 70,254 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 124 ms
20,224 KB |
testcase_01 | AC | 2,892 ms
20,244 KB |
testcase_02 | AC | 1,413 ms
20,224 KB |
testcase_03 | AC | 257 ms
20,224 KB |
testcase_04 | AC | 223 ms
20,224 KB |
testcase_05 | AC | 190 ms
20,224 KB |
testcase_06 | AC | 189 ms
20,224 KB |
testcase_07 | AC | 158 ms
20,224 KB |
testcase_08 | AC | 191 ms
20,224 KB |
testcase_09 | AC | 157 ms
20,224 KB |
testcase_10 | AC | 647 ms
20,224 KB |
testcase_11 | AC | 454 ms
20,352 KB |
testcase_12 | AC | 651 ms
20,224 KB |
testcase_13 | AC | 551 ms
20,352 KB |
testcase_14 | AC | 685 ms
20,224 KB |
testcase_15 | AC | 619 ms
20,224 KB |
testcase_16 | AC | 651 ms
20,352 KB |
testcase_17 | AC | 684 ms
20,224 KB |
testcase_18 | AC | 586 ms
20,340 KB |
testcase_19 | AC | 655 ms
20,352 KB |
testcase_20 | AC | 2,857 ms
20,352 KB |
testcase_21 | AC | 2,859 ms
20,352 KB |
testcase_22 | TLE | - |
testcase_23 | AC | 2,597 ms
20,352 KB |
testcase_24 | AC | 2,829 ms
20,224 KB |
testcase_25 | AC | 2,829 ms
20,224 KB |
testcase_26 | AC | 2,819 ms
20,224 KB |
testcase_27 | AC | 2,883 ms
20,280 KB |
testcase_28 | AC | 2,927 ms
20,224 KB |
testcase_29 | AC | 2,789 ms
20,224 KB |
testcase_30 | AC | 2,900 ms
20,404 KB |
testcase_31 | TLE | - |
testcase_32 | AC | 2,833 ms
20,224 KB |
testcase_33 | AC | 2,855 ms
20,224 KB |
testcase_34 | TLE | - |
testcase_35 | AC | 2,861 ms
20,224 KB |
testcase_36 | AC | 2,988 ms
20,352 KB |
testcase_37 | AC | 2,845 ms
20,224 KB |
testcase_38 | AC | 59 ms
20,352 KB |
testcase_39 | AC | 91 ms
20,352 KB |
testcase_40 | AC | 2,757 ms
20,224 KB |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(ll i=0;i<n;i++)#define repl(i,l,r) for(ll i=(l);i<(r);i++)#define per(i,n) for(ll i=(n)-1;i>=0;i--)#define perl(i,r,l) for(ll i=r-1;i>=l;i--)#define fi first#define se second#define pb push_back#define ins insert#define pqueue(x) priority_queue<x,vector<x>,greater<x>>#define all(x) (x).begin(),(x).end()#define CST(x) cout<<fixed<<setprecision(x)#define vtpl(x,y,z) vector<tuple<x,y,z>>#define rev(x) reverse(x);using ll=long long;using vl=vector<ll>;using vvl=vector<vector<ll>>;using pl=pair<ll,ll>;using vpl=vector<pl>;using vvpl=vector<vpl>;const ll MOD=1000000007;const ll MOD9=998244353;const int inf=1e9+10;const ll INF=4e18;const ll dy[9]={0,1,-1,0,1,1,-1,-1,0};const ll dx[9]={1,0,0,-1,1,-1,1,-1,0};template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}const int mod = 1000000007;const int max_n = 1000050;struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}mint operator+(const mint a) const { return mint(*this) += a;}mint operator-(const mint a) const { return mint(*this) -= a;}mint operator*(const mint a) const { return mint(*this) *= a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}bool operator==(const mint &p) const { return x == p.x; }bool operator!=(const mint &p) const { return x != p.x; }// for prime modmint inv() const { return pow(mod-2);}mint& operator/=(const mint a) { return *this *= a.inv();}mint operator/(const mint a) const { return mint(*this) /= a;}};istream& operator>>(istream& is, mint& a) { return is >> a.x;}ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}using vm=vector<mint>;using vvm=vector<vm>;struct combination {vector<mint> fact, ifact;combination(int n):fact(n+1),ifact(n+1) {assert(n < mod);fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n-k];}}comb(max_n);//O(N^3logk)//https://yukicoder.me/submissions/733933//https://atcoder.jp/contests/abc236/submissions/28778130using vec=vector<mint>;using matrix=vector<vector<mint>>;matrix matmul(matrix &left,matrix &right){int n=left.size();matrix ret(n,vec(n));//+の単位元で埋めるfor(int i=0;i<n;i++){for(int k=0;k<n;k++){//ループ順序の最適化for(int j=0;j<n;j++){ret[i][j]+=left[i][k]*right[k][j];}}}return ret;}matrix matpow(matrix &mat,ll k){int n=mat.size();matrix ret(n,vec(n));//+の単位元で埋めるfor(int i=0;i<n;i++)ret[i][i]=1;//*の単位元で埋めるwhile(k){if(k&1)ret=matmul(mat,ret);k>>=1;if(k)mat=matmul(mat,mat);}return ret;}vec update(matrix &mat,vec &v){int n=mat.size();vec ret(n);//+の単位元で埋めるfor(int i=0;i<n;i++){for(int j=0;j<n;j++){ret[i]+=mat[i][j]*v[j];}}return ret;}int main(){ll l,n,m;cin >> l >> n >> m;vvm mat(240,vm(240));//vl v(11);rep(i,m){ll a;cin >> a;v[a]++;}for(int i=1;i<=n;i++){//末尾の数字for(int j=1;j<=11;j++){//繰り返しfor(int p=1;p<=n;p++){for(int q=1;q<=11;q++){ll to=(p-1)*12+q,from=(i-1)*12+j;if(i==p){if(j!=11&&j+1==q)mat[to][from]=1;if(j==11&&q==11)mat[to][from]=1;}else{if(v[i]==1){if(q==1&&j==i)mat[to+120][from]=1;else if(q==1){mat[to][from]=1;}}else{if(q==1)mat[to][from]=1;}}from+=120;to+=120;if(i==p){if(j!=11&&j+1==q)mat[to][from]=1;if(j==11&&q==11)mat[to][from]=1;}else{if(v[i]==1){if(q==1)mat[to][from]=1;}else{if(q==1)mat[to][from]=1;}}}}}}for(int i=1;i<=n;i++)mat[i*12-12+1][0]=1;/*rep(i,25){rep(j,25){cout << mat[i][j] <<" ";}cout << endl;}*/mat=matpow(mat,l);/*rep(i,25){rep(j,25){cout << mat[i][j] <<" ";}cout << endl;}*/vm dp(240);dp[0]=1;dp=update(mat,dp);mint ans=0;repl(i,120,240)ans+=dp[i];for(int i=1;i<=10;i++){if(v[i]){ans+=dp[i*12-12+i];}}cout << ans << endl;}