10分做法

是人都会，不讲解

20-40分做法

$k=2$时

$(x+1)^2$ 展开 $x^2+2x+1$ 与原项作差得到 $2x+1$ 故每次1操作的贡献为 $\sum_{i=1}^{cnt} (2x_i+1)=\sum_{i=1}^{cnt}2x_i+cnt$ 其中$cnt$为此前操作0的次数。 设$sum$为$x_i$的和,每次操作0 $sum+=x$, 操作1 $sum+=cnt$,即可$O(1)$回答每次询问

$k=3$时

同理,$(x+1)^3$与$x^3$作差得到$3x^2+3x+1$ 用$sum2$来 维护$x_i^2$的和，每次更新完$ans$后再依次更新$sum2$和$sum$

100分做法

观察$k=2$和$k=3$时,都是将$(x+1)^k$与$x^k$作差,再维护$x_i^p(p\in[1,k-1])$的和，乘以对应系数即可得到操作1的贡献,故$k<=50$时同样考虑展开后作差,但是要得到每一项的系数，闲着没事也可以自己展开$(x+1)^{50}$,这里提供正常做法

二项式定理

$(a+b)^n=\sum_{i=0}^{n}C_{n}^{i}a^{n-i}b^i$ 代入到本题为 $(x+1)^k=\sum_{i=0}^{k}C_{k}^{i}x^{k-i}$ 减去$x^k$后,操作1的贡献即为 $\sum_{i=0}^{cnt}\sum_{j=1}^{k}C_{k}^{j}x_i^{k-j}$ 交换顺序得到 $\sum_{j=1}^{k}C_{k}^{j}\sum_{i=0}^{cnt}x_i^{k-j}$ 用$sum[i]$来维护$x^i$的和,贡献为 $\sum_{j=1}^{k}C_{k}^{j}sum[k-j]$ 组合数数组的求法可以用逆元，也可以递推，这里不作说明。 每次操作0从1到k更新sum,操作1从k到1更新sum,即可$O(k)$回答每次询问,$O(k^2)$更新sum,总复杂度为$O(Mk^2)$ (数组一定要记得开大点,小熊猫没有越界报错考时过了大样例以为稳了，结果出来全re发现是数组开小了，开成c[70][70]就a了o(╥﹏╥)o) 代码:

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
#define int long long
#define reg register
#define FOR(i,a,b) for(reg int i=(a);i<(b);++i)
#define ROF(i,a,b) for(reg int i(a);i>=(b);--i)
#define Endl endl
constexpr int MAXN = (int)1e5+10;
constexpr int INF = 0x3f3f3f3f;
constexpr int mod = (int)1e9+7;
inline int max(const int& lhs,const int& rhs){
	return lhs>rhs?lhs:rhs;
}
inline int min(const int& lhs,const int& rhs){
	return lhs<rhs?lhs:rhs;
}
int n,k,op,x,c[70][70],sum[60];
inline void init(){
	FOR(i,0,61){
		c[i][0] = 1;
		FOR(j,1,i+1){
			c[i][j] = (c[i-1][j]+c[i-1][j-1]+mod)%mod;
		}
	}
}
inline int quick_pow(int x,int k){
	int ret = 1;
	while(k){
		if(k&1) ret = ret*x%mod;
		x = x*x%mod;
		k >>= 1;
	}
	return ret;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("out.txt","w",stdout);
	cin>>n>>k;
	init();
	memset(sum,0,sizeof(sum));
	FOR(i,0,n){
		cin>>op;
		if(op){
			for(reg int i=k;i;--i)
				FOR(j,1,i+1)
					sum[i] = (sum[i]+c[i][j]*sum[i-j])%mod;//sum((x+1)^k)-x^k=sum(C(i,k)*x^(k-i)) (1<=i<=k)
			cout<<sum[k]%mod<<endl;
		}else{
			cin>>x;
			++sum[0];
			FOR(j,1,k+1) sum[j] = (sum[j]+quick_pow(x,j))%mod;
			cout<<sum[k]%mod<<endl;
		}
	}
	return 0;
}