Editorial for SPBINARY2
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MOD = 1000000000; int f[1000111], s[1000111]; int main() { int n, k; scanf("%d%d", &n, &k); f[0] = s[0] = 1; FOR(i,1,k) { f[i] = (f[i-1] * 2) % MOD; s[i] = (s[i-1] + f[i]) % MOD; } FOR(i,k+1,n) { f[i] = (s[i-1] - s[i-k-1] + MOD) % MOD; s[i] = (s[i-1] + f[i]) % MOD; } cout << f[n] << endl; return 0; }
Code mẫu của hieult
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <cmath> //#include <conio.h> #define ep 0.00001 #define oo 1000000010 #define mod 1000000000 double const PI=4*atan(1); int f[1111111],n,k; using namespace std; int main(){ // freopen("A.in","r",stdin); // freopen("A.out","w",stdout); scanf("%d %d",&n,&k); f[0] = 2; f[1] = 2; for(int i = 2;i<=n;i++){ if(i<=k) f[i] = (f[i-1]*2)%mod; else f[i] = (f[i-1]*2-f[i-k-1])%mod; if(f[i]<0) f[i]+=mod; } printf("%d\n",f[n]); // getch(); }
Comments