现在不会放题解的！比赛完了我会把题解放上来的
祝大家玩的愉快~
等会，cnblogs不会显示更新时间？
我禁赛我自己
UPD：2018.12.15
欢迎大家爆踩标程～
painting
我们考虑转化题意，题目要求
[sumlimits_{i_1=1}^nsumlimits_{i_2=i_1+opt}^n...sumlimits_{i_m=i_{m-1}+opt}^n1
]
然后我们分情况讨论一下
- 若opt=1，那么答案即为(inom{n}{m})
- 若opt=0，那么序列(i_1,i_2,...,i_m)必然是个不减序列，我们令(A_k=i_k+k)，那么序列(A)必然是个严格递增序列，并且取值在((1,n+m])，所以答案即为(inom{n+m-1}{m})（插板法同样可以解决）
然后注意求(inom{n}{m})需要for循环，复杂度(O(Tm))
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1;char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1e6,p=1e9+7;
int inv[N+10];
int C(ll n,int m){
if (n<m) return 0;
int res=1;
for (int i=1;i<=m;i++) res=1ll*res*((n-i+1)%p)%p*inv[i]%p;
return res;
}
int main(){
inv[1]=1;
for (int i=2;i<=N;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
for (int Data=read();Data;Data--){
ll n; int m,opt;
scanf("%lld%d%d",&n,&m,&opt);
printf("%d
",opt?C(n,m):C(n+m-1,m));
}
return 0;
}
sequence
我们打表可得，(A_1=2,A_2=3,A_i=A_{i-1}+A_{i-2}-[i\%2==0])，然后记录三个信息矩阵快速幂一下，复杂度(O(T*3^3log n))，只有40pts(常数优秀的大佬应该可以有100pts)，然鹅吸个氧就可以过了（滑稽
不过考试时不能吸氧，于是我们考虑优化，但这个式子已经不好优化了，那么我们换个思路(其实是我不知道怎样优化这个式子)，令(x=dfrac{1+sqrt{5}}{2},y=dfrac{1-sqrt{5}}{2})，不难发现(x,y)恰好为(t^2=t+1)的两个解。我们构造数列(F_n=F_{n-1}+F_{n-2})，则(x,y)为(F_n)的两个特征根。我们令(F_n=x^n+y^n)，把(n=1,2)代入得到(F_1=1,F_2=3)，然后我们进行分类讨论：
- 当(n)为奇数，则有(-1<y^n<0)，此时(lceil x^n ceil(A_n)=F_n+1)
- 当(n)为偶数，则有(0<y^n<1)，此时(lceil x^n ceil(A_n)=F_n)
所以我们只要求出(F_n)，即可求出(A_n)，因为(F_n=F_{n-1}+F_{n-2})，所以我们使用矩阵快速幂即可，复杂度(O(T*2^3log n))
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1;char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int p=998244353;
struct Matrix{
int v[2][2];
Matrix(){memset(v,0,sizeof(v));}
void clear(){memset(v,0,sizeof(v));}
void init(){for (int i=0;i<2;i++) v[i][i]=1;}
}A,B;
Matrix operator *(const Matrix &x,const Matrix &y){
Matrix z;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
z.v[i][k]=(z.v[i][k]+1ll*x.v[i][j]*y.v[j][k])%p;
return z;
}
Matrix mlt(Matrix a,ll b){
Matrix res; res.init();
for (;b;b>>=1,a=a*a) if (b&1) res=res*a;
return res;
}
int main(){
A.v[0][0]=A.v[0][1]=A.v[1][0]=1;
for (int T=read();T;T--){
ll n; scanf("%lld",&n);
B.v[0][0]=3,B.v[0][1]=1;
if (n<=2){
printf(n==1?"2
":"3
");
continue;
}
B=B*mlt(A,n-2);
printf("%d
",B.v[0][0]+(int)(n&1));
}
return 0;
}
polynomial
显然有(sumlimits_{i=0}^na^ib^{n-i}=dfrac{a^{n+1}-b^{n+1}}{a-b})，不过万恶的出题人为了卡掉这个做法，选择了读入膜数(p)，这样就导致(a-b)可能不存在(\%p)意义下的逆元……(a掉出题人)
这题我们考虑分治，对(n)的奇偶性进行讨论：
- 若(n)为奇数，则有(sumlimits_{i=0}^na^ib^{n-i}=(sumlimits_{i=0}^{lfloor n/2 floor}a^ib^{lfloor n/2 floor-i}) imes(a^{lfloor n/2 floor+1}+b^{lfloor n/2 floor+1}))
- 若(n)为偶数，则有(sumlimits_{i=0}^na^ib^{n-i}=(sumlimits_{i=0}^{n/2}a^ib^{n/2-i}) imes(a^{n/2}+b^{n/2})-a^{n/2}b^{n/2})
注意在计算(a^{n/2},b^{n/2})的时候不能使用快速幂，应该在递归的时候不断平方，否则时间复杂度是(O(Tlog^2 n))，这样显然是过不了的
然后注意由于(p)过大，乘起来会爆long long，于是我们可以用__int128……（如果没记错我应该是卡了int128，但是吸口氧应该能过）
化乘为加也不行，会给复杂度添个(log)（无良出题人啊），因此我们使用下面这个乘法
typedef long long ll;
typedef long double ld;
ll mlt(ll _a,ll _b,ll _p){
ll _c=ld(_a)*_b/_p;
ll _ans=_a*_b-_c*_p;
if (_ans<0) _ans+=_p;
return _ans;
}
乘的过程中，如果溢出了就不管了，反正两个部分溢出的是一样的，相减即可把溢出部分消掉。(你要相信出题人用的也是这个，不然他造不了数据)
ps：对于所有的数据点，化乘为加与该乘法输出答案相同
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
#define sqr(x) mlt(x,x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
ll a,b,n,p,Afac,Bfac;
ll mlt(ll _a,ll _b){
ll _c=ld(_a)*_b/p;
ll _ans=_a*_b-_c*p;
if (_ans<0) _ans+=p;
return _ans;
}
ll work(ll n){
if (n<=1) return !n?1:(a+b)%p;
ll sum=work(n>>1);
Afac=sqr(Afac),Bfac=sqr(Bfac);
if (n>>1&1) Afac=mlt(Afac,a),Bfac=mlt(Bfac,b);
return n&1?mlt(mlt(Afac,a)+mlt(Bfac,b),sum):(mlt(Afac+Bfac,sum)-mlt(Afac,Bfac)+p)%p;
}
int main(){
for (int Data=read();Data;Data--){
scanf("%lld%lld%lld%lld",&n,&a,&b,&p),Afac=Bfac=1;
printf("%lld
",(work(n)+p)%p);
}
return 0;
}
fibonacci
这题首先想到树剖，但是直接树剖完全无法维护，因此我们需要知道Fibonacci数列的一个性质：(Fib_{n+m}=Fib_{m-1}*Fib_{n}+Fib_{m}*Fib_{n+1})(证明请自行百度)
那么对于每个点加的值(Fib_{D+k})，我们可以将其改为(Fib_d+k')((d)为该点在树上的深度，且(D+k=d+k'))，那么每个点加的值为(Fib_{d-1}*Fib_{k'}+Fib_d*Fid_{k'+1})(或者其他方式)，因为(k'=D-d+k)，且(D-d)是个定值，所以(k')是个定值，因此我们只要对于每个节点维护好(Fib_{d-1},Fib_{d})，就可以用树剖+线段树维护其系数，细节可以看下代码
就算(k')是负数也没关系，你可以用负数去尝试，依然满足该性质，(Fib_{k'})使用(Fib_{k'+2}=Fib_{k'}+Fib_{k'+1})倒序求即可（或者可以用(Fib_{-n}=(-1)^{n-1}Fib_{n})求得，我使用后者）
由于(k')达到了(10^{18})，所以我们需要用矩乘求(Fib_{k'})(矩乘是不是有点多啊……)
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
int x=0,f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline int read(){
int x=0,f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=1e5,Mod=1e9+7;
int n,m;
struct Node{
int x,y;
Node(){x=y=0;}
Node(int _x,int _y){x=_x,y=_y;}
Node operator +(const Node &tis)const{return Node((x+tis.x)%Mod,(y+tis.y)%Mod);}
int operator *(const Node &tis)const{return (1ll*x*tis.x+1ll*y*tis.y)%Mod;}
};
struct Matrix{
int v[2][2];
Matrix(){memset(v,0,sizeof(v));}
void init(){for (int i=0;i<2;i++) v[i][i]=1;}
}trans;
Matrix operator *(const Matrix &x,const Matrix &y){
Matrix z;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
z.v[i][k]=(z.v[i][k]+1ll*x.v[i][j]*y.v[j][k])%Mod;
return z;
}
Matrix mlt(Matrix a,ll b){
Matrix res; res.init();
for (;b;b>>=1,a=a*a) if (b&1) res=res*a;
return res;
}
Node Fib(ll x){
Matrix res; res.v[0][1]=1;
res=res*mlt(trans,x<0?-x-1:x);
if (x>=0) return Node(res.v[0][0],res.v[0][1]);
res.v[0][(-x-1)&1]=-res.v[0][(-x-1)&1];
return Node(res.v[0][1],res.v[0][0]);
}
void init(){trans.v[0][1]=trans.v[1][0]=trans.v[1][1]=1;}
int v[N+10],dfn[N+10],ID[N+10];
struct S1{
#define ls (p<<1)
#define rs (p<<1|1)
struct node{
int sum;
Node val,tag;
}tree[(N<<2)+10];
void updata(int p){
tree[p].val=tree[ls].val+tree[rs].val;
tree[p].sum=(tree[ls].sum+tree[rs].sum)%Mod;
}
void Add_tag(int p,Node v){
tree[p].sum=(tree[p].sum+tree[p].val*v)%Mod;
tree[p].tag=tree[p].tag+v;
}
void pushdown(int p){
if (!tree[p].tag.x&&!tree[p].tag.y) return;
Add_tag(ls,tree[p].tag);
Add_tag(rs,tree[p].tag);
tree[p].tag=Node(0,0);
}
void build(int p,int l,int r){
if (l==r){
tree[p].val=Fib(v[dfn[l]]);
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
updata(p);
}
void Modify(int p,int l,int r,int x,int y,Node v){
if (x<=l&&r<=y){
Add_tag(p,v);
return;
}
pushdown(p);
int mid=(l+r)>>1;
if (x<=mid) Modify(ls,l,mid,x,y,v);
if (y>mid) Modify(rs,mid+1,r,x,y,v);
updata(p);
}
int Query(int p,int l,int r,int x,int y){
if (x<=l&&r<=y) return tree[p].sum;
int mid=(l+r)>>1,res=0;
pushdown(p);
if (x<=mid) res=(res+Query(ls,l,mid,x,y))%Mod;
if (y>mid) res=(res+Query(rs,mid+1,r,x,y))%Mod;
return res;
}
#undef ls
#undef rs
}ST;//Segment Tree
struct S2{
int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],tot,Time;
int deep[N+10],fa[N+10],size[N+10],top[N+10],Rem[N+10];
void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}
void insert(int x,int y){join(x,y),join(y,x);}
void dfs(int x){
deep[x]=deep[fa[x]]+1,size[x]=1,v[x]=deep[x];
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
if (son==fa[x]) continue;
fa[son]=x,dfs(son);
size[x]+=size[son];
if (size[Rem[x]]<size[son]) Rem[x]=son;
}
}
void build(int x){
if (!x) return;
dfn[ID[x]=++Time]=x;
top[x]=Rem[fa[x]]==x?top[fa[x]]:x;
build(Rem[x]);
for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){
if (son==Rem[x]||son==fa[x]) continue;
build(son);
}
}
int work(int x,int y){
int res=0;
while (top[x]!=top[y]){
if (deep[top[x]]<deep[top[y]]) swap(x,y);
res=(res+ST.Query(1,1,n,ID[top[x]],ID[x]))%Mod;;
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
res=(res+ST.Query(1,1,n,ID[x],ID[y]))%Mod;;
return res;
}
}HLD;//Heavy Light Decomposition
int main(){
init(); char s[5];
n=read(),m=read();
for (int i=1;i<n;i++){
int x=read(),y=read();
HLD.insert(x,y);
}
HLD.dfs(1),HLD.build(1),ST.build(1,1,n);
for (int i=1;i<=m;i++){
scanf("%s",s);
if (s[0]=='U'){
int x=read(); ll k;
scanf("%lld",&k);
k-=v[x]+1;
ST.Modify(1,1,n,ID[x],ID[x]+HLD.size[x]-1,Fib(k));
}
if (s[0]=='Q'){
int x=read(),y=read();
printf("%d
",HLD.work(x,y));
}
}
return 0;
}