给出(k)，记树高为(k)满二叉树（(2^k-1)个节点）的prufer序(i)个为(p_i)，若干个询问，每次询问(a,d,m)表示求(sum_{i=0}^{m-1}p_{a+di})
(kle 30,Qle 300)
时间(7s)。
做题的时候只枚举了(kle 4)的prufer序，找到错误规律……
看到(Qle 300)和那么多的时间，就应该发觉这不是数学题而是爆搜题。
首先分析一下这个prufer序如何构造：显然是对根的左子树进行后序遍历，往prufer序中输出遍历到的每个点的父亲，然后遍历根，然后递归到右子树的子问题。
定义(F(x,k))和(G(x,k))分别表示根没有父亲和根有父亲的序列，序列中的每个元素用多项式表示。(x)表示根节点是什么。
那么有：(F(x,k)=G(2x,k-1)+{x}+{2x+1}+F(2x+1,k-1))，(G(x,k)=G(2x,k-1)+{x}+G(2x+1,k-1)+{x})
如果没有推出通项，题目中的这条东西不太好求。于是可以考虑暴力，以(2^b)分一块计算。每一块都有询问((a,d,m))，在这块内计算出多项式之后用这一块的根节点的值代进去。
由于多项式是一样的，所以可以一起算，只算两种块：(F(x,b))和(G(x,b))。可以(O(2^bb))或(O(2^b))地求出块内每个数，然后(O(2^{2b}))地做个前缀和，这样每个块就可以(O(1))询问了。询问的时候要拆成(2^{k-b})个块。于是时间为(O(2^{2b}+Q2^{k-b}))。
因为不想把空间开太大，所以我的程序中(b)取了(10)。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define B 10
#define ll long long
int k,b,Q;
struct poly{
ll p,q;
poly(ll _p=0,ll _q=0){
p=_p,q=_q;
}
poly f(poly g){
return poly(p*g.p,p*g.q+q);
}
ll f(ll x){
return p*x+q;
}
};
poly operator+(poly a,poly b){return poly(a.p+b.p,a.q+b.q);}
poly operator-(poly a,poly b){return poly(a.p-b.p,a.q-b.q);}
int len(int k){return (1<<k)-2;}
poly queryg(int x,int k){
if (k==2){
assert(x==1 || x==2);
return poly(1,0);
}
if (x<=len(k-1)) return queryg(x,k-1).f(poly(2,0));
if (x==len(k-1)+1) return poly(1,0);
if (x<=len(k-1)+1+len(k-1)) return queryg(x-len(k-1)-1,k-1).f(poly(2,1));
return poly(1,0);
}
poly queryf(int x,int k){
if (k==2){
assert(x==1);
return poly(1,0);
}
if (x<=len(k-1)) return queryg(x,k-1).f(poly(2,0));
if (x==len(k-1)+1) return poly(1,0);
if (x==len(k-1)+2) return poly(2,1);
return queryf(x-len(k-1)-2,k-1).f(poly(2,1));
}
struct data{
poly h[1<<B],s[1<<B][1<<B];
void init(poly query(int,int),int n){
for (int i=1;i<=n;++i){
h[i]=query(i,b);
// printf("(%lld,%lld)
",h[i].p,h[i].q);
}
// printf("
");
for (int j=1;j<n;++j){
for (int i=n-j+1;i<=n;++i)
s[j][i]=h[i];
for (int i=n-j;i>=1;--i)
s[j][i]=s[j][i+j]+h[i];
// for (int i=1;i<=len(b);++i)
// printf("(%lld,%lld) ",s[j][i].p,s[j][i].q);
// printf("
");
}
}
} F,G;
ll ans;
void calc(int c,int a,int d,int m,int t){
if ((c-a)%d) return;
int tmp=(c-a)/d;
if (0<=tmp && tmp<=m)
ans+=t;
}
void divideg(int k,int a,int d,int m,int t){
if (k==b){
ans+=(m==0?G.h[a]:(G.s[d][a]-(a+(m+1)*d<=len(b)?G.s[d][a+(m+1)*d]:poly(0,0)))).f(t);
return;
}
calc(len(k-1)+1,a,d,m,t);
calc(len(k-1)+1+len(k-1)+1,a,d,m,t);
if (a+d*m==len(k-1)+1+len(k-1)+1){
if (m==0) return;
m--;
}
if (a<=len(k-1))
divideg(k-1,a,d,min(m,(len(k-1)-a)/d),t*2);
if (a+d*m>len(k-1)+1){
int tmp=(a>len(k-1)+1?0:(len(k-1)+1-a+1 +d-1)/d);
divideg(k-1,a+tmp*d-len(k-1)-1,d,m-tmp,t*2+1);
}
}
void dividef(int k,int a,int d,int m,int t){
if (k==b){
ans+=(m==0?F.h[a]:(F.s[d][a]-(a+(m+1)*d<=len(b)?F.s[d][a+(m+1)*d]:poly(0,0)))).f(t);
return;
}
calc(len(k-1)+1,a,d,m,t);
calc(len(k-1)+2,a,d,m,t*2+1);
if (a<=len(k-1))
divideg(k-1,a,d,min(m,(len(k-1)-a)/d),t*2);
if (a+m*d>len(k-1)+2){
int tmp=(a>len(k-1)+1?0:(len(k-1)+2-a+1 +d-1)/d);
dividef(k-1,a+tmp*d-len(k-1)-2,d,m-tmp,t*2+1);
}
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&k,&Q);
b=min(B,k);
G.init(queryg,(1<<b)-2);
F.init(queryf,(1<<b)-3);
// for (int i=1;i<=(1<<k)-3;++i){
// ans=0;
// dividef(k,i,1,0,1);
// printf("%lld
",ans);
// }
// return 0;
while (Q--){
int a,d,m;
scanf("%d%d%d",&a,&d,&m);
assert(d);
ans=0;
dividef(k,a,d,m-1,1);
// ll sum=0;
// for (int i=0;i<m;++i)
// sum+=queryf(a+d*i,k).f(1);
// assert(ans==sum);
printf("%lld
",ans);
}
return 0;
}