Typical DP Contest

Submission #5886634

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class ll>using V=vector<ll>;
template<class ll>using VV=V<V<ll>>;
template<class ll,class Y>ostream& operator<<(ostream& o,const pair<ll,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename ll>void Fill(A (&array)[N],const ll&v){fill((ll*)array,(ll*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

struct Kitamasa{
  int k;
  vector<ll> tmp, tmp2, v, r;
  ll mod;
  void _next(vector<ll>&a){
    ll b = a[k-1];
    for(int i=k-1; i>0; i--) a[i] = (b*v[i]+a[i-1])%mod;
    a[0] = b*v[0]%mod;
  };
  void _twice(vector<ll>&a){
    tmp = vector<ll>(k, 0ll);
    tmp2 = a;
    for(int i=0; i<k; i++){
      for(int j=0; j<k; j++) (tmp[j] += a[i]*tmp2[j]) %= mod;
      _next(tmp2);
    }
    swap(tmp, a);
  };
  void _calc(ll n){
    if(n<k){
      r = vector<ll>(k, 0ll);
      r[n] = v[n];
    }else if(n<k*2){
      r = v;
      for(int i=k; i<n; i++) _next(r);
    }else if(n%2){
      _calc(n/2);
      _twice(r);
      _next(r);
    }else{
      _calc(n/2);
      _twice(r);
    }
  }
  vector<ll> calc(vector<ll>&_v, ll n, ll _mod){
    v = _v;
    k = v.size();
    mod = _mod;
    tmp.resize(k);
    _calc(n);
    return r;
  }
};
Kitamasa K;
ll k, n;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> k >> n;
  vector<ll> a(k, 1ll), b=K.calc(a, n-1, MOD);
  ll ans = 0;
  FOR(i, 0, k) ans += b[i];
  cout << ans%MOD << endl;
}

Submission

Task問題 T - フィボナッチ
User nameユーザ名 char134217728
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 8
Source lengthソースコード長 3255 Byte
File nameファイル名
Exec time実行時間 403 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
All 8 / 8 00,01,02,03,04,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 AC 403 ms 256 KB
01 AC 220 ms 256 KB
02 AC 401 ms 256 KB
03 AC 69 ms 256 KB
04 AC 1 ms 256 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB