自己收集整理的一些模板= - （毕业了就整理一下
……
……
……
*your soul will be so sweet*
const int Mx=1252,MOD=100000000;
struct BIGN{
int a[Mx+10];
BIGN(){memset(a,0,sizeof a);}
int &operator [](int i){return a[i];}
inline void operator /=(int x){
for(int i=Mx;i>=1;--i)
a[i-1]+=a[i]%x*MOD,a[i]/=x;
}
inline void operator -=(BIGN &b){
for(int i=1;i<Mx;++i)
a[i]=a[i]-b[i]+(a[i-1]+MOD)/MOD -1,a[i-1]=(a[i-1]+MOD)%MOD;
}
inline void operator +=(BIGN &b){
Mx;
for(int i=1;i<=Mx;++i)a[i]+=b[i];
for(int i=1;i<=Mx;++i)if(a[i]>=MOD)++a[i+1],a[i]%=MOD;
}
inline void operator *=(int x){
for(int i=1;i<Mx;++i)
a[i]=a[i]*x+a[i-1]/MOD,a[i-1]%=MOD;
}
inline bool operator <(BIGN &b){
for(int i=Mx;i>=1;--i)
if(a[i]!=b[i]) return a[i]<b[i];
return false;
}
inline bool iszero(){
for(int i=1;i<Mx;++i)if(a[i]!=0)return false;
return true;
}
inline void read(){
char tp[10005]={'0','0','0','0','0','0','0','0'};
scanf("%s",tp+8);
int len=strlen(tp+1),p=1;
while(len-8*p+1>0)
sscanf(tp+len-8*p+++1,"%8d",&a[p]);
}
inline void print(){
int p=Mx;
while(!a[p]&&p>0) p--;
printf("%d",a[p--]);
while(p>0) printf("%08d",a[p--]);
printf("\n");
}
};
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define oo (1<<30)
#define N 100005
#define M 1000005
int n,S,T,ll,son[N],d[N],q[N],link[M],next[M],cap[M],opp[M];
inline int min(int x,int y){return x<y?x:y;}
bool build(){
int x,y,l=1,r=1;
memset(d,-1,sizeof(int)*(n+5));
q[1]=S;d[S]=0;
while(l<=r){
x=q[l++];
for(int i=son[x];i!=-1;i=next[i]){
y=link[i];
if(cap[i]&&d[y]==-1){
d[y]=d[x]+1;q[++r]=y;
if(y==T)return 1;
}
}
}
return 0;
}
int find(int now,int flow){
int ret,y,w=0;
if(now==T)return flow;
for(int i=son[now];i!=-1&&w<flow;i=next[i]){
y=link[i];
if(cap[i]&&d[y]==d[now]+1&&(ret=find(y,min(flow-w,cap[i]))))
cap[i]-=ret,cap[opp[i]]+=ret,w+=ret;
}
if(!w)d[now]=-1;
return w;
}
void addedge(int x,int y,int z){
link[++ll]=y;next[ll]=son[x];son[x]=ll;cap[ll]=z;opp[ll]=ll+1;
link[++ll]=x;next[ll]=son[y];son[y]=ll;cap[ll]=0;opp[ll]=ll-1;
}
int main(){
int m,x,y,z,ans,flow;
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
while(~scanf("%d%d",&m,&n)){
memset(son,-1,sizeof(int)*(n+5));
S=1;T=n;ans=0;ll=0;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&x,&y,&z),addedge(x,y,z);
while(build())
while(1){
flow=find(S,oo);
if(!flow)break;
ans+=flow;
}
printf("%d\n",ans);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
//fread->read
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
inline void read(ll &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
inline void read(double &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
inline void read(char *s){
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
inline void read(char &c){
for (c=nc();blank(c);c=nc());
if (IOerror){c=-1;return;}
}
//getchar->read
inline void read1(int &x){
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
inline void read1(ll &x){
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
inline void read1(double &x){
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (ch=='.'){
double tmp=1;
for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
}
if (bo)x=-x;
}
inline void read1(char *s){
char ch=getchar();
for (;blank(ch);ch=getchar());
for (;!blank(ch);ch=getchar())*s++=ch;
*s=0;
}
inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
//scanf->read
inline void read2(int &x){scanf("%d",&x);}
inline void read2(ll &x){
#ifdef _WIN32
scanf("%I64d",&x);
#else
#ifdef __linux
scanf("%lld",&x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void read2(double &x){scanf("%lf",&x);}
inline void read2(char *s){scanf("%s",s);}
inline void read2(char &c){scanf(" %c",&c);}
inline void readln2(char *s){gets(s);}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(double x,int y){
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if (x<-1e-12)out('-'),x=-x;x*=mul[y];
ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
}
void println(double x,int y){print(x,y);out('\n');}
void print(char *s){while (*s)out(*s++);}
void println(char *s){while (*s)out(*s++);out('\n');}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
//puts->write
char Out[OUT_SIZE],*o=Out;
inline void print1(int x){
static char buf[15];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(int x){print1(x);*o++='\n';}
inline void print1(ll x){
static char buf[25];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(ll x){print1(x);*o++='\n';}
inline void print1(char c){*o++=c;}
inline void println1(char c){*o++=c;*o++='\n';}
inline void print1(char *s){while (*s)*o++=*s++;}
inline void println1(char *s){print1(s);*o++='\n';}
inline void println1(){*o++='\n';}
inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
struct puts_write{
~puts_write(){flush1();}
}_puts;
inline void print2(int x){printf("%d",x);}
inline void println2(int x){printf("%d\n",x);}
inline void print2(char x){printf("%c",x);}
inline void println2(char x){printf("%c\n",x);}
inline void print2(ll x){
#ifdef _WIN32
printf("%I64d",x);
#else
#ifdef __linux
printf("%lld",x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x){print2(x);printf("\n");}
inline void println2(){printf("\n");}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace fastIO;
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n,x,sum=0;long long lx;char str[105],ch;
println(3.01,2);flush();
print(-1);print(' ');
println2(123456789123456789LL);
println(-3.141592653589,10);
println(2.9999,2);
read2(ch);println2(ch);
read1(lx);println(lx);
read(n);
for (int i=1;i<=n;++i)read(x),sum+=x;
printf("%d\n",sum);
read(str);
puts(str);
print1("zzy dhh");
println("zhazha frog");
flush1(); flush();
system("pause");for (;;);
return 0;
}
/*
input:
A
123456789123456789
3
1 10 100
nie&&ga!
output:
3.01
123456789123456789
A
111
nie&&ga!
zzy dhh
-1 -3.1415926536
3.00
123456789123456789
zhazha frog
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
namespace fastIO{
#define BUF_SIZE 100000
//fread->read
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void read(int &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
inline void read(double &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
inline void read(char *s){
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
//getchar->read
inline void read1(int &x){
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
inline void read1(double &x){
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (ch=='.'){
double tmp=1;
for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
}
if (bo)x=-x;
}
void read1(char *s){
char ch=getchar();
for (;blank(ch);ch=getchar());
for (;!blank(ch);ch=getchar())*s++=ch;
*s=0;
}
//scanf->read
void read2(int &x){scanf("%d",&x);}
void read2(double &x){scanf("%lf",&x);}
void read2(char *s){scanf("%s",s);}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)*s1++='-',x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(char *s){
while (*s)out(*s++);out('\n');
}
void flush(){
if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}
}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void print(char *s){Ostream.print(s);}
inline void flush(){Ostream.flush();}
//puts->write
char Out[BUF_SIZE],*o=Out;
inline void print1(int x){
static char buf[15];
char *p1=buf;if (!x)*p1++='0';if (x<0)*p1++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1; *o++='\n';
}
inline void print1(char *s){
while (*s)*o++=*s++; *o++='\n';
}
inline void flush1(){if (o!=Out)*--o=0;puts(Out);}
#undef BUF_SIZE
};
using namespace fastIO;
int main(){
freopen("1.in","r",stdin);
freopen("fastIO_fread.out","w",stdout);
int t1=clock();
int n,x;read(n);
for (int i=1;i<=n;++i)read(x);
printf("time=%d\n",clock()-t1);
fclose(stdin);fclose(stdout);
freopen("1.in","w",stdout);
srand(time(0));t1=clock();
n=10000000;printf("%d\n",n);
for (int i=1;i<=n;++i)print(rand()*rand());
flush();
fclose(stdout);
freopen("fastIO_fwrite.out","w",stdout);
printf("time=%d\n",clock()-t1);
fclose(stdout);
//system("pause");for (;;);
return 0;
}
//v1.5.0→v2.0.0 大大缩短代码but大幅度增加内存&提升速度
//v2.0.0→v2.1.0 提升速度
namespace Read{
const int S=5000000;
char _str[S],*p=_str;
inline int read(){
int x=0;for(;*p<'0'||*p>'9';++p);
while(*p>='0'&&*p<='9')x=x*10+*p++-48;
return x;
}
}
using Read::read;
char buf[10],out[6000005],*o=out;
inline void print(int x){
char *b=buf;if (!x)*b++='0';
while(x){*b++=x%10+48;x/=10;}
while(b--!=buf)*o++=*b;
*o++='\n';
}
//处理负数
namespace Read{
const int S=5000000;
char _str[S],*p=_str;
inline void read(int &x){
bool f;
x=0;for(;(*p<'0'||*p>'9')&&(*p!='-');p++);
if(*p=='-')f=true,++p;else f=false;
while(*p>='0'&&*p<='9')x=x*10+*p++-48;
if(f)x=-x;
}
}
using Read::read;
char buf[10],out[6000005],*o=out;
inline void print(int x){
char *b=buf;if (!x)*b++='0';
if(x<0){*o++='-';x=-x;}
while(x){*b++=x%10+48;x/=10;}
while(b--!=buf)*o++=*b;
*o++='\n';
}
fread(Read::p,1,Read::S,stdin);
puts(out);
//v2.1.0→v3.0.0 内存大大减小，代码增长一倍,速度稍微变慢
//v3.0.0→v3.4.0 内存减小到固定100k 代码进行优化
//v3.4.0→v3.5.5 代码优化
//v3.5.5→v3.6.0 增添补丁、输出优化（小内存）
//v3.6.0→v3.7.2 提升速度，优化代码
//v3.7.2→v3.7.6 增添简洁版
namespace fastIO{
#define S 100000
bool IOerror=0;
inline char nc(){
static char buf[S],*p1=buf+S,*pend=buf+S;
if(p1==pend){p1=buf;pend=buf+fread(buf,1,S,stdin);if(pend==p1)return IOerror=1,-1;}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline int read(){
char ch=nc();int x=0;for(;blank(ch);ch=nc());
if(IOerror)return -1;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
return x;
}
#undef S
};
using namespace fastIO;
//简洁版（不适用补丁）
#define S 100000
inline char nc(){
static char buf[S],*p1=buf+S,*pend=buf+S;
if(p1==pend){p1=buf;pend=buf+fread(buf,1,S,stdin);if(pend==p1)return-1;}
return *p1++;
}
inline int read(){
char ch=nc();int x=0;for(;ch<'0'||ch>'9';ch=nc());
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return x;
}
//输出优化(补丁)：
struct Fast_print{
char *buf,*p1,*pend;
Fast_print(){buf=new char[S];p1=buf;pend=buf+S;}
inline void out(char ch){if(p1==pend)fwrite(buf,1,S,stdout),p1=buf;*p1++=ch;}
inline void print(int x){
static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)*s1++='-',x=-x;
while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);//out('\n');
}
void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Fast_print(){flush();}
}so_Fast;
inline void print(int x){so_Fast.print(x);}
//补丁
inline int read(){
bool sign=0;char ch=nc();int x=0;for(;blank(ch);ch=nc());
if(IOerror)return -1;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(sign)x=-x;return x;
}
inline void read(double &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(ch=='.'){
double tmp=1;ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if(sign)x=-x;
}
inline void read(char *s){
char ch=nc();
for(;blank(ch);ch=nc());
if(IOerror)return;
for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
inline void read(char &c){
for(c=nc();blank(c);c=nc());
if(IOerror){c=-1;return;}
}
#define ll long long
inline void read(ll &x){
bool sign=0;char ch=nc();x=0;
for(;blank(ch);ch=nc());
if(IOerror)return;
if(ch=='-')sign=1,ch=nc();
for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
}
//力
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<complex>
#include<cmath>
#define pi 3.141592653589793238462643383
using namespace std;
typedef complex<double>E;
E f[300003],_f[300003],g[300003],e1[300003],e2[300003];
int n,L,m,rev[300003];
inline void fft(E *a,int f){
for(int i=0;i<n;++i)if(i>rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<n;i<<=1){
E wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=(i<<1)){
E w(1,0);
for(int k=0;k<i;++k,w*=wn){
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
if(f==-1)for(int i=0;i<n;++i)a[i]/=n;
}
int main(){
scanf("%d",&n);--n;
for(int i=0;i<=n;++i){
double x;scanf("%lf",&x);
f[i]=x,_f[n-i]=x;
}
m=2*n;for(n=1;n<=m;n<<=1)++L;
for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
for(int i=1;i<=n;++i)g[i]=(1.0/i/i);
fft(f,1),fft(_f,1),fft(g,1);
for(int i=0;i<n;++i)e1[i]=f[i]*g[i];
for(int i=0;i<n;++i)e2[i]=_f[i]*g[i];
fft(e1,-1),fft(e2,-1);
for(int i=0;i<=m/2;++i)printf("%.3lf\n",e1[i].real()-e2[m/2-i].real());
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll quickpow(ll m,ll n,ll k){int b=1;while(n>0){if(n&1)b=(b*m)%k;n=n>>1;m=(m*m)%k;}return b;}
inline ll read(){
char ch;ll a=0;bool f=false;
ch=getchar();while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
if(ch!='-')a*=10,a+=ch-'0';else f=true;
while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
if(f)a=-a;return a;
}
void gcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b)d=a,x=1,y=0;
else gcd(b,a%b,d,y,x),y-=x*(a/b);
}
inline ll mul_mod(ll a,ll b,ll n){return a*b%n;}
inline ll inv(ll a,ll n){
ll d,x,y;
gcd(a,n,d,x,y);
return d==1?(x+n)%n:-1;
}
inline ll log_mod(ll a,ll b,ll n){
ll m=(ll)sqrt(n+0.5),v=inv(quickpow(a,m,n),n),e=1,i;
map<int,int>x;
x[1]=0;
for(i=1;i<m;++i){
e=mul_mod(e,a,n);
if(!x.count(e))x[e]=i;
}
for(i=0;i<m;i++){
if(x.count(b))return i*m+x[b];
b=mul_mod(b,v,n);
}
return -1;
}
int main(){
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
int T=read(),Q=read();
while(T--){
ll a=read(),b=read(),p=read();
if(Q==1)printf("%lld\n",quickpow(a,b,p));
else if(Q==2){
ll x=quickpow(a,p-2,p)*b%p;
if(x*a%p==b%p)printf("%lld\n",x);
else puts("Orz, I cannot find x!");
}else{
ll x=log_mod(a,b,p);
if(x==-1)puts("Orz, I cannot find x!");
else printf("%lld\n",x);
}
}
}
void rmq_init(){
int i,j,t;
for(j=1;j<=n;j++)mx[j][0]=mn[j][0]=h[j];
int m=floor(log((double)n)/log(2.0));
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
t=j+(1<<(i-1));
if(t<=n)mx[j][i]=max(mx[j][i-1],mx[t][i-1]);
else mx[j][i]=mx[j][i-1];
}
}
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
t=j+(1<<(i-1));
if(t<=n)mn[j][i]=min(mn[j][i-1],mn[t][i-1]);
else mn[j][i]=mn[j][i-1];
}
}
}
int rmq(int l,int r){
int m=floor(log((double)(r-l+1))/log(2.0));
int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
return a-b;
}
void tarjan(int x){
low[x]=dfn[x]=++dfs_clock;
inq[x]=1,q[++top]=x;
for(int i=last[x];i;i=e[i].next)
if(!dfn[e[i].to])tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
if(low[x]==dfn[x]){
int now=0;++scc;
for(;x!=now;now=q[top],--top,bl[now]=scc,inq[now]=0,++num[scc]);
}
}
/*
ID:hqztrue1
LANG:C++
TASK:ditch
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
const int maxn=20010;
const int maxm=500010;
#define oo 50000000
int son[maxn],q[maxn],d[maxn],pre[maxn];
int link[maxm],st[maxm],next[maxm],cap[maxm],opp[maxm],cost[maxm];
int n,m,i,S,T,ll,ans,maxflow,mincost;
int x,y,z;
void addedge(int x,int y,int z,int c){
link[++ll]=y;st[ll]=x;next[ll]=son[x];son[x]=ll;cap[ll]=z;cost[ll]=c;opp[ll]=ll+1;
link[++ll]=x;st[ll]=y;next[ll]=son[y];son[y]=ll;cap[ll]=0;cost[ll]=-c;opp[ll]=ll-1;
}
int spfa(int s){
int h=1,t=1,i,j,p;
memset(d,6,sizeof(int)*(n+5));
d[S]=0;q[1]=S;
while (h<=t){
i=q[h++];
for(p=son[i];p!=-1;p=next[p]){
j=link[p];
if(d[i]+cost[p]<d[j]&&cap[p]){
d[j]=d[i]+cost[p];
pre[j]=p;q[++t]=j;
}
}
}
return d[T]>oo?0:1;
}
void update(){
int p,flow=oo;
for(p=T;p!=S;p=st[p]){
p=pre[p];if(cap[p]<flow)flow=cap[p];
}
maxflow+=flow;
for(p=T;p!=S;p=st[p]){
p=pre[p];mincost+=cost[p]*flow;
cap[p]-=flow;cap[opp[p]]+=flow;
}
}
int main(){
//srand(time(0));
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
ll=0;scanf("%d%d",&m,&n);
memset(son,-1,sizeof(int)*(n+5));
S=1;T=n;maxflow=mincost=0;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z,rand()&32767);
}
while (spfa(S))update();
printf("%d\n",maxflow);
//printf("%d\n",mincost);
//system("pause");
return 0;
}
//by Rxd
//height
void Get_Height(){
int k=0;
for(int i=0;i<n;i++){
if(k)k--;
int j=SA[x[i]-1];
while(s[i+k]==s[j+k])k++;
Height[x[i]]=k;
}
}
//SA
void Build_SA(){
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)c[x[i]=s[i]]++;
for(int i=1;i<m;i++)c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)SA[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int cnt=0;
for(int i=n-k;i<n;i++)y[cnt++]=i;
for(int i=0;i<n;i++)
if(SA[i]>=k)y[cnt++]=SA[i]-k;
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)c[x[y[i]]]++;
for(int i=1;i<m;i++)c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)SA[--c[x[y[i]]]]=y[i];
swap(x,y);
cnt=1;x[SA[0]]=0;
for(int i=1;i<n;i++)
x[SA[i]]=(y[SA[i-1]]==y[SA[i]]&&y[SA[i-1]+k]==y[SA[i]+k]?cnt-1:cnt++);
if(cnt>=n)break;
m=cnt;
}
}
/*#include<cstdio>
using namespace std;
int a[300][300],b[300][300],c[300][300];
int main(){
int n,m,p;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d%d",&m,&p);
for(int i=1;i<=m;i++)
for(int j=1;j<=p;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
if(j==p)printf("%d\n",c[i][j]);
else printf("%d ",c[i][j]);
}*/
#include<cstring>
#include<cstdio>
#include<algorithm>
const int p=10000;
using namespace std;
struct node{
long long k[3][3];
}m,tt;
node ju(node a,node b){
node c;
memset(c.k,0,sizeof(c.k));
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++){
c.k[i][j]=0;
for(int k=1;k<=2;k++){
c.k[i][j]+=(a.k[i][k]*b.k[k][j])%p;
c.k[i][j]=c.k[i][j]%p;
}
}
return c;
}
int main(){
while(1){
int n;
scanf("%d",&n);
if(n==-1)break;
if(n==0){
printf("0\n");
continue;
}
n-=1;
tt.k[1][2]=1;
tt.k[1][1]=tt.k[2][1]=tt.k[2][2]=0;
m.k[1][1]=0;
m.k[1][2]=m.k[2][1]=m.k[2][2]=1;
while(n>0){
if(n&1)tt=ju(tt,m);
n=n>>1;
m=ju(m,m);
}
printf("%d\n",tt.k[1][2]);
}
}
/*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 sum(int x){
int ret=0;
while(x>0)ret+=c[x],x-=lowbit(x);
return ret;
}
void add(int x,int d){
while(x<=n)c[x]+=d,x+=lowbit(x);
}
loading...
评论 (0)
