/ Vijos / 题库 / 数列 /

# 149 条题解

• @ 2014-01-05 21:43:51

二进制
分析很简单的,只要有点数学思维即可.当然我已开始分析出来的数是
1
01
11
001
101
.......
第i列如果是1,表示这个数得加上k^n.其中第n行表示第n个数
只要反转过来就是递增的了,1,2,3,4,5,6,7,8,9

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define N 100
#define M 100

int main()
{
int i,j,k,n;
int a[16];
scanf("%d%d",&k,&n);
a[0] = 1; j = 0;
for (i = 0;i < 13;i++) {
a[i+1] = a[i]*k;
if (n&(1<<i))
j += a[i];
}
printf("%d",j);

return 0;
}

• @ 2021-08-29 17:01:26
``````#include <bits/stdc++.h>
using namespace std;

long long k, n, ans;
stack<int> S;
int main() {
cin >> k >> n;
while(n) S.push(n & 1), n >>= 1;
while(!S.empty()) ans += S.top() * pow(k, S.size()-1), S.pop();
cout << ans << endl;
return 0;
}
``````
• @ 2021-03-17 09:46:04
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
int K,N;

void main()
{
scanf("%d%d",&K,&N);
int ans=0;
for (int i=0,delta=1;i<=10;i++,delta*=K)
if ((1<<i)&N)
ans+=delta;
printf("%d\n",ans);
}
};

int main()
{
dts::main();
}
``````
• @ 2017-05-11 13:50:20

不用long long 主程序三行。。。当年的pj第四题那么水吗

``````#include <bits/stdc++.h>
using namespace std;
int x,t,sum,now=1;
int main()
{
scanf("%d%d",&x,&t);
for(;t;t>>=1){if(t&1) sum+=now;now*=x;}
printf("%d",sum);
}

``````
• @ 2016-09-15 20:38:41
``````var //cho:array[1..2000] of longint;
k,{i,l,}t,n:longint;
ans:int64;

begin
{l:=0;
repeat
inc(l);
cho[l+1]:=cho[l] div k;
cho[l]:=cho[l] mod k;
until cho[l+1]=0;}
t:=1;ans:=0;
while n<>0 do begin
inc(ans,t*(n and 1));
t:=t*k;n:=n div 2;
//writeln(ans);
end;
writeln(ans);
//writeln(l)
end.
``````
• @ 2015-09-11 13:26:39

k^0+k^1+k^2+......+k^n < k^n+1 (k>=3)
var sum,a,k,n,now:longint;
z:array[1..10000]of longint;
begin
sum:=1; now:=1;
z[now]:=sum;
repeat
inc(now);
sum:=sum*k;
z[now]:=sum;
for a:=1 to now-1 do
z[now+a]:=z[now]+z[a];
now:=now<<1-1;
until now>=n;
writeln(z[n]);
end.

• @ 2016-12-28 12:49:30

#include <bits/stdc++.h>
using namespace std;
int k,n;
long long ans,tot=1; //long long 很重要。
int main()
{
cin>>k>>n;
while(n){
ans+=n%2*tot; //tot 表示这一位k进制下的权值
n/=2; //标准二进制
tot=tot*k; //每次乘以k
}cout<<ans; //用cout输出
return 0;
}

• @ 2016-11-17 09:11:12

感觉我的好复杂，，，，

#include<algorithm>
#include<cstdio>
using namespace std;
int num[20]={0};
int pud(int x,int n){
int tol=1;
for(int i=1;i<=n;i++)
tol=tol*x;
}
int main(){
int n,i,j;
int k;
int ans=0;
scanf("%d %d",&n,&k);
for(i=0;;i++){
num[i]=k%2,k=k/2;
if(k<2) {
num[++i]=k;
break;
}
}
for(j=0;j<=i;j++)
ans=ans+num[j]*pud(n,j);
printf("%d\n",ans);
return 0;
}

• @ 2016-08-08 14:54:30

世上竟有如此水题
```c++
#include<iostream>
using namespace std;

int ans;
int k, N;

int main ()
{
cin >> k >> N;
int p = 1;
for (int i = 0; i < 10; i++) {
if (N & (1 << i)) ans += p;
p *= k;
}
cout << ans;
return 0;
}
```

• @ 2016-08-07 21:44:52

暴力解法
``` c++
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 300000 + 5;
unsigned long long m, n, ans;
vector<unsigned long long> vec;

unsigned long long poer(unsigned long long a,int b)
{
unsigned long long tot=1;
for(int i = 1; i <= b; i++) tot *= a;
}

void work(){
int N = n*5, mi = 0;
while(N > 0){
vec.push_back(poer(m,mi++)); N--;
int len = vec.size() - 1;
for(int i = 0; i < len; i++){
vec.push_back(vec[len] + vec[i]); N--;
}

}
sort(vec.begin(), vec.end());
}

int main() {
cin >> m >> n;
work();
cout << vec[n-1];
return 0;
}
```

• @ 2016-03-19 14:16:50

我居然用了107行。。。
测试数据 #0: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 808 KiB, score = 10
Accepted, time = 0 ms, mem = 812 KiB, score = 90
```pascal
type int=longint;
var
n,ans:real;
t,step,s,ss,i,k,m,te,j:int;
flag:boolean;
z:array[0..16]of int;
w:array[0..1000]of real;
procedure qsort(l,r:int);
var
i,j:int;
m,p:real;
begin
i:=l; j:=r; m:=w[(l+r) div 2];
repeat
while w[i]<m do inc(i);
while w[j]>m do dec(j);
if i<=j then
begin
p:=w[i];
w[i]:=w[j];
w[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

function c(x,y:int):int;
var
a,b,i:int;
begin
a:=1; b:=1;
for i:=y downto y-x+1 do a:=a*i;
for i:=1 to x do b:=b*i;
exit(a div b);
end;

procedure f(x,y:int);
var
i:int;
begin
if x=1 then
begin
for i:=y+1 to k-1 do
begin
inc(step);
if step=te then
begin
inc(t);
z[t]:=i;
flag:=true;
end;
end;
exit;
end;
for i:=y+1 to k-1 do
begin
f(x-1,i);
if flag then
begin
inc(t);
z[t]:=i;
exit;
end;
end;
end;

begin
s:=1;
ss:=1;
k:=0;
repeat
inc(k);
ss:=ss*2;
s:=s+ss;
until s>=m;
m:=m-ss;
ans:=exp(k*ln(n));
if m=0 then
begin
writeln(ans:0:0);
halt;
end;
for j:=1 to s-ss do
begin
te:=j;
t:=0;
flag:=false;
step:=0;
w[j]:=ans;
for i:=1 to k do
begin
te:=te-c(i,k);
if te<=0 then
begin
te:=te+c(i,k);
f(i,-1);
break;
end;
end;
for i:=1 to t do w[j]:=w[j]+exp(z[i]*ln(n));
end;
qsort(1,s-ss);
writeln(w[m]:0:0);
end.
```

• @ 2015-11-19 19:57:05

本题数据规模较小，可采用二进制数的思路解题。首先，将读入的n分解为二进制数，后按位展开……还是看程序注释吧。
###Pascal Code
program p1319;
var
k,n,i,c,ans:longint;
a:array[0..11] of 0..1; //记录二进制数的数组

cp:array[0..11] of longint; //由于数据实在太弱，又不想一次次递归（强迫症），可以开个数组存k的i次幂

procedure TB; //把n分解二进制，就不解释了
begin
c:=0;

while n>0 do
begin
a[c]:=n mod 2;

n:=n div 2;
inc(c);
end;
dec(c);
end;

procedure FB; //把二进制数组按位展开
begin
ans:=0; //初始化结果
for i:=c downto 0 do //这里倒序正序都没关系
if a[i]=1 then ans:=ans+cp[i]; //直接打幂表的好处,打幂表子程序在下面
end;

procedure P; //打幂表
var
t:longint;
begin
cp[0]:=1; //任何数的0次方都是1
t:=1;
for i:=1 to 11 do
begin
t:=t*k;
cp[i]:=t;
end;
end;

begin //main
fillchar(a,sizeof(a),0);
P;
TB;
FB;
writeln(ans);
end.

• @ 2015-10-10 20:58:03

评测状态 Accepted
题目 P1319 数列
递交时间 2015-10-10 20:57:38
代码语言 C++
评测机 VijosEx
消耗时间 82 ms
消耗内存 528 KiB
评测时间 2015-10-10 20:57:39
评测结果
编译成功

测试数据 #0: Accepted, time = 11 ms, mem = 524 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 528 KiB, score = 10
测试数据 #4: Accepted, time = 9 ms, mem = 528 KiB, score = 10
测试数据 #5: Accepted, time = 6 ms, mem = 528 KiB, score = 10
测试数据 #6: Accepted, time = 5 ms, mem = 528 KiB, score = 10
测试数据 #7: Accepted, time = 5 ms, mem = 528 KiB, score = 10
测试数据 #8: Accepted, time = 1 ms, mem = 528 KiB, score = 10
Accepted, time = 82 ms, mem = 528 KiB, score = 90
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int ans=0;
bool num[1010];
int poer(int a,int b)
{
int tot=1;
for(int i=1;i<=b;i++)tot*=a;
}
int main()
{
int n,k;
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++)
{
for(int cnt=0;;cnt++){
num[cnt]=!num[cnt];
if(num[cnt]==true)
break;
}

}
for(int i=0;i<=1000;i++)
if(num[i])ans+=poer(k,i);
printf("%d",ans);
}

• @ 2015-06-25 21:39:25

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int k,n,a[1000000],ans;
int main(){
cin>>k>>n;
int nn=n,len;
int i=1;
while(nn>0){
a[i]=nn%2;
nn/=2;
i++;
}
len=i-1;

for(int r=1;r<=len;r++){
if(a[r]==1){
int tot=1;
for(int e=1;e<r;e++){
tot*=k;
}
ans+=tot;
}
}
cout<<ans;
return 0;
}

• @ 2014-12-26 17:29:46

var
m:array[0..110] of longint;
m2:array[0..22] of longint;
se:array[0..10000] of longint;
k,n,i,j,last:longint;
label 8;
function mcf(a:longint):longint;
begin
if m[a]<>0 then exit(m[a]);
if a=0
then begin
m[a]:=1;
exit(1);
end;
m[a]:=mcf(a-1)*k;
exit(m[a]);
end;
begin
fillchar(m,sizeof(m),0);
last:=0;
se[0]:=0;
m2[0]:=1;
for i:=1 to 22 do
m2[i]:=m2[i-1]*2;
for i:=0 to trunc(ln(n)/ln(2)) do //最高指数
begin
for j:=last+1 to last+m2[i] do //最高指数为i的所有项
begin
se[j]:=se[j-last-1]+mcf(i);
if j=n then goto 8;
end;
last:=last+m2[i];
end;
8:writeln(se[n]);
end.

• @ 2014-11-25 20:34:53

#include<iostream>
using namespace std;
main()
{
long long a[1001],b,i,j,k,l=-1,n;
cin>>k>>n;
while(n!=0)
{
a[++l]=n%2;
n/=2;
}
for(i=0;i<=l;i++)
if(a[i]==1)
{
b=1;
for(j=1;j<=i;j++)
b*=k;
n+=b;
}
cout<<n;
}

• @ 2014-10-29 16:55:29

var
a:array[0..10000] of longint;
i,j,k,n:longint;
w,t:int64;
begin
fillchar(a,sizeof(a),0);
j:=0;
while n>0 do
begin
a[j]:=n mod 2;
n:=n div 2;
inc(j);
end;
t:=0;
w:=1;
for i:=0 to j do
begin
t:=t+w*a[i];
w:=w*k;
end;
write(t);
end.

• @ 2014-08-16 19:09:51

var
a:array[0..10000] of longint;
i,j,k,n:longint;
w,t:int64;
begin
fillchar(a,sizeof(a),0);
j:=0;
while n>0 do
begin
a[j]:=n mod 2;
n:=n div 2;
inc(j);
end;
t:=0;
w:=1;
for i:=0 to j do
begin
t:=t+w*a[i];
w:=w*k;
end;
write(t);
end.

• @ 2012-10-26 22:18:17

编译通过...

├ 测试数据 01：答案正确... (0ms, 580KB)

├ 测试数据 02：答案正确... (0ms, 580KB)

├ 测试数据 03：答案正确... (0ms, 580KB)

├ 测试数据 04：答案正确... (0ms, 580KB)

├ 测试数据 05：答案正确... (0ms, 580KB)

├ 测试数据 06：答案正确... (0ms, 580KB)

├ 测试数据 07：答案正确... (0ms, 580KB)

├ 测试数据 08：答案正确... (0ms, 580KB)

├ 测试数据 09：答案正确... (0ms, 580KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 580KB

农夫山泉有点甜

• @ 2010-07-14 13:24:13

再加上分治

#include

using namespace std;

int k,n,len,tot,i;

int f[100];

bool is_known[100],bin[100];

int calc(int n)

{

int i,j;

if(is_known[n])return f[n];

if(n%2==0)

{

f[n]=calc(n/2)*calc(n/2);

is_known[n]=true;

return f[n];

}

f[n]=calc(n/2)*calc(n/2)*k;

is_known[n]=true;

return f[n];

}

int main()

{

freopen("sequence.in","r",stdin);

freopen("sequence.out","w",stdout);

scanf("%d%d",&k,&n);

f[0]=1;is_known[0]=true;

len=1;

while(n!=1)

{

bin[len]=n%2;

n=n/2;

len++;

}

bin[len]=true;

for(i=1;i

ID
1319

1

2437

1609

66%

19