距阵的乘法,关键是要熟悉距阵乘法的结合率,可以用N*LOGN的算法过。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int a11, a12;
int a21, a22;
}type;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Mul ( type *a, type *b, type *c )//a*b->c
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
c->a11 = ( a->a11*b->a11 + a->a12*b->a21 ) % 10000;
c->a12 = ( a->a11*b->a12 + a->a12*b->a22 ) % 10000;
c->a21 = ( a->a21*b->a11 + a->a22*b->a21 ) % 10000;
c->a22 = ( a->a21*b->a12 + a->a22*b->a22 ) % 10000;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Cpy ( type *a, type *b )//a=b
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
a->a11 = b->a11;
a->a12 = b->a12;
a->a21 = b->a21;
a->a22 = b->a22;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
type sum, count, temp, t;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) type e = { 1, 0, 0, 1 };
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) type s = { 1, 1, 1, 0 };
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &n ) != EOF && n >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( n == 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "0\n" );
continue;
}
if ( n == 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "1\n" );
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n = n-2;
Cpy ( &sum, &e );
Cpy ( &count, &s );
while ( n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( n & 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
Mul ( &sum, &count, &temp );
Cpy ( &sum, &temp );
}
n >>= 1;
Cpy ( &t, &count );
Mul ( &count, &t, &temp );
Cpy ( &count, &temp );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", ( sum.a11 + sum.a12 ) % 10000 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
用二维的树状数组做的,但是速度很慢,不知道对不对。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
__int64 tree[LEN][LEN]; //记录区间里面的线段数目
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init_t ( int n, int m )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=m; j++ )
tree[i][j] = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline int cupk ( int a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return a&(-a);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void add ( int n, int m, int i, int j, int num )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int ii=i; ii<n; ii+=cupk ( ii ) )
for ( int jj=j; jj<m; jj+=cupk ( jj ) )
tree[ii][jj] += num;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline __int64 ser ( int i, int j )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int sum = 0;
for ( int ii=i; ii>=1; ii-=cupk ( ii ) )
for ( int jj=j; jj>=1; jj-=cupk ( jj ) )
sum += tree[ii][jj];
return sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
scanf ( "%d", &t );
for ( int c=1; c<t+1; c++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int n, m, k;
scanf ( "%d%d%d", &n, &m, &k );
init_t ( n, m );
__int64 ans = 0;
for ( int i=0; i<k; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int a, b;
scanf ( "%d%d", &a, &b );
__int64 k = 0;
if ( a>1&&b<m )
k += ser ( a-1, m )-ser ( a-1, b );
if ( a<n&&b>1 )
k += ser ( n, b-1 )-ser ( a, b-1 );
ans += k;
add ( n+1, m+1, a, b, 1 );
}
printf ( "Test case %d: %I64d\n", c, ans );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
线性的算法,记录最近的分数,最后约分。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gdc(int a, int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (a==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return b;
}
if (b==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return a;
}
return gdc(b, a%b);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n, d;
int i;
double min;
int mn, md;
int men, med;
double minest;
int temp;
int pub;
double t1, t2;
while (scanf("%d%d", &n, &d) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
minest = 1;
pub = gdc(n, d);
n = n/pub;
d = d/pub;
for (i=1; i<=32767; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = 1;
temp = (int)((double)i * (double)n / (double)d);
pub = gdc(i, temp);
if (temp/pub!=n || i/pub!=d)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ((double)n/(double)d-(double)temp/(double)i < (double)(temp+1)/(double)i-(double)n/(double)d)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = (double)temp/(double)i;
mn = temp;
md = i;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min = (double)(temp+1)/(double)i;
mn = temp+1;
md = i;
}
}
t1 = min-(double)n/(double)d>0 ? min-(double)n/(double)d:(double)n/(double)d-min;
t2 = minest-(double)n/(double)d>0 ? minest-(double)n/(double)d:(double)n/(double)d-minest;
if (t1<t2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
minest = min;
men = mn;
med = md;
}
}
pub = gdc(men, med);
printf("%d %d\n", men/pub, med/pub);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
摘要: 题目看着向生成树,但实际上是最短路径+堆优化。
#include <stdio.h>const int LEN = 50005;const __int64 MAX = 0x7fffffffffffffff; struct HEAD{ &nbs... 阅读全文
摘要: 素数的入门题目,素数表+线性查找,OK!
#include<iostream.h>long data[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,1... 阅读全文
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|