53 条题解
-
4
wszq LV 10 @ 2008-12-24 17:50:08
n-1个必含A或C共有X=4^(n-1)-2^(n-1)，其中奇数个A偶数个C、奇数个A奇数个C、偶数个A奇数个C、偶数个A偶数个C都各分别有X/4,而奇数个A偶数个C加个A，偶数个A奇数个C加个C，偶数个A偶数个C加个T或G都可得到符合要求的n个含A或C的字符序列，再加上不含A或C的2^n个,
即共有X/4+X/4+2*X/4+2^n=4^(n-1)-2^(n-1)+2^n=2^(n-1)*(2^(n-1)+1)。 -
1
這個數據。。莫名奇妙的，結果是2輸出的是2也不是輸出02，結果是0反而要輸出00。真心無語。貼上帶有莫名喜感的代碼：
#include<iostream> using namespace std; int table[20] = {52, 4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76}; int work(int n) { if (n < 3) return (1 << (2 * n - 2)) + (1 << (n - 1)); else return (table[(2 * n - 3) % 20] + table[(n - 2) % 20]) % 100; } int main() { int n; cin >> n; int ans; while (n) { ans = work(n); if (ans) cout << work(n) << endl; else cout << "00" << endl; cin >> n; } return 0; }公式：ans=(2^(2n-2)+2^(n-1))%100
-
0
feidaoluoye LV 9 @ 2017-11-21 18:05:42
#include <iostream> #include<cstdlib> #include<cstdio> #include<map> #include<vector> #include<cstring> #include<algorithm> #define mod 100 #define FOR(i,x,y) for(i=x;i<=y;++i) #define maxa 10000+100 using namespace std; int main() { long long n; while(cin>>n&&n) { long long t =1,i =0; while(i<n-1) { t = t*2; t%=mod; i++; } t%=mod; long long ans = t*(t+1); ans%=mod; cout<<ans<<endl; } } -
0
指数型母函数。。。。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int ans[25]; int main() { int n; while ( scanf("%d",&n) && n != 0) { for (int j=1;j<=24;j++) { int a1 = 1,a2 = 1; for (int i=0;i<j-1;i++) { a1 = a1 * 2 % 100; a2 = a2 * 4 % 100; } ans[j] = (a1+a2) % 100; } if (n>=4) { n %= 20; if (n < 4) n += 20; } if (ans[n] == 0) cout<<"00"<<endl; else cout<<ans[n]<<endl; } return 0; } -
0
设f(i)表示长度为i的序列 中有偶数个a 偶数个c 的个数
设g(i)表示长度为i的序列 中有奇数个a 偶数个c 的个数
设h(i)表示长度为i的序列 中有偶数个a 奇数个c 的个数
设m(i)表示长度为i的序列 中有奇数个a 奇数个c 的个数
f(i)=2*f(i-1)+g(i-1)+h(i-1) //任意一个f序列加g或t都可以 其他同理
g(i)=2*g(i-1)+f(i-1)+m(i-1)
h(i)=2*h(i-1)+f(i-1)+m(i-1)
m(i)=2*m(i-1)+g(i-1)+h(i-1)
剩下来用矩阵快速幂可以在logn的复杂度内解决
构造递推矩阵
2 1 1 0
1 2 0 1
1 0 2 1
0 1 1 2
然后乘矩阵
f(i-1)
g(i-1)
h(i-1)
m(i-1)即可得到一个新的矩阵
f(i)
g(i)
h(i)
m(i)
由于矩阵满足结合律 快速幂即可
接下来是代码#include <cstdio>
using namespace std;struct matrix{//矩阵类
int mat[10][10];
void clear(){for(int i=1;i<10;i++)for(int j=1;j<10;j++)mat[i][j]=0;}
void as1(){clear(); for(int i=1;i<10;i++)mat[i][i]=1;}//定义为单位矩阵
void operator = (matrix x){for(int i=1;i<10;i++)for(int j=1;j<10;j++)mat[i][j]=x.mat[i][j];}
friend matrix operator * (matrix a,matrix b){
matrix c;
c.clear();
for(int i=1;i<10;i++)
for(int j=1;j<10;j++)
for(int k=1;k<10;k++)
(c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%100)%=100;
return c;
}
}a,b,c,d;//矩阵a为转移矩阵，b为单位矩阵，c为初始值，d为结果int n;
int main(){
for(scanf("%d",&n);n!=0;scanf("%d",&n)){
if(n==1) printf("2\n");
else if(n==2) printf("6\n");
else {
a.clear(),b.as1();c.clear();//记得初始化
for(int i=1;i<=4;i++) a.mat[i][i]=2;
for(int i=2;i<=3;i++) a.mat[1][i]=a.mat[4][i]=a.mat[i][1]=a.mat[i][4]=1;
c.mat[1][1]=1;c.mat[2][1]=0;c.mat[3][1]=0;c.mat[4][1]=0;
while(n){
if(n&1) b=b*a;//用b保存结果
a=a*a;
n>>=1;
}//快速幂
d=c*b;
printf("%02d\n",d.mat[1][1]);//0的时候要输出00
}
}
return 0;
} -
0
测试数据 #0: Accepted, time = 0 ms, mem = 444 KiB, score = 100
纯属找规律
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int a[11] = {2,6,20,72,72,56,60,12,92,56};
int b[21] = {0,52,12,56,40,92,32,56,80,32,52,56,20,72,72,56,60,12,92,56};
int main() {
int n;
while(~ scanf("%I64d", &n),n) {
if(n <= 10) {
n -- ;
printf("%d\n",a[n]);
} else {
if(b[(n - 11) % 20] == 0) printf("00\n");
else printf("%d\n",b[(n - 11) % 20]);
}}
return 0;
} -
0
这道题考的是传说中的指数型母函数.
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<time.h>
#include<stdlib.h>
using namespace std;
int f(int d, int n){
if (n == 0)return 1;
int t = (n >> 1);
int p = f(d, t);
p *= p;
if (n & 1)p *= d;
p %= 100;
return p;
}
int main(){
freopen("in.txt", "r", stdin);
int n;
while (cin >> n&&n != 0){
int four = f(4, n - 1);
int two = f(2, n - 1);
four += two;
if (four % 100 == 0)cout << "00" << endl;
else cout << four % 100 << endl;
}
return 0;
} -
0
太不容易了 用一个搜索推出了表达式
2^n-1*(2^n-1+1)
然后突然发现x=11的时候要输出00而不是0！！！这个害我各种WA
最后注意的是0作为结束的标志要break
看看我丑陋的代码吧 我是渣渣一个#include<iostream>
#include<cstdio>
using namespace std;
long long int s ,ans;
int quickpow(int m,int n,int k)
{
int b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}
int main()
{
while(cin>>s){
if(s==0)
{
break;
}
ans=quickpow(2,s-1,100)*(quickpow(2,s-1,100)+1);
if(ans%100==0)
{
cout<<"00"<<endl;
}
elsecout<<ans%100<<endl;
}//system("pause");
return 0;
} -
0
-
0
-
l610002858 @ 2015-07-22 08:21:44
发假题解很好玩吗？多少次看到这名字了，还TM是假题解
-
-
0
First_blood LV 9 @ 2009-11-05 23:33:52
就一个点，过起来超级不爽的说
- -|||
-
0
song19931218 LV 9 @ 2009-09-20 19:38:38
program p1077;
var
n,yu1,yu2:longint;
procedure kuaisumi(base,n:longint; var yu:longint);
begin
if n=1 then yu:=base mod 100
else
begin
kuaisumi(base,n div 2,yu);
yu:=(yu*yu) mod 100;
if n mod 2=1 then yu:=(yu*base) mod 100;
end;
end;
begin
read(n);
while n0 do
begin
if n=1 then write(2)
else
begin
kuaisumi(4,n-1,yu1);
kuaisumi(2,n-1,yu2);
yu1:=(yu1+yu2) mod 100;
if yu1=0 then writeln('00') else writeln(yu1);
end;
read(n);
end;
end.
第一次忘了对n=1的特判。。。。WA了
第二次忘了对最后两位为0的情况特殊处理，又WA了。。。。。。。。。。。。
第三次。。。啊，终于AC了 -
0
mintalfance LV 10 @ 2009-09-08 11:44:37
program p1077;
var i,j,k,l,m,n:longint;
function brick(x,y:longint):longint;
var g,t,s:longint;
begin
if y=0 then exit(1);
if y=1 then exit(x);
if y mod 2=0 then begin
g:=brick(x,y div 2);
s:=(g*g) mod 100; exit(s); end
else begin g:=brick(x,y div 2);
s:=(g*g*x) mod 100; exit(s); end;
end;
begin
readln(n);
while n0 do begin
m:=(brick(2,n-1)+brick(4,n-1)) mod 100;
if m=0 then writeln('00') else writeln(m);
readln(n);
end;
end.快速幂啊快速幂
wszq
LV 10
@ 2008-12-24 17:50:08
