算法备赛模板（临时）（一）

#include<bits/stdc++.h>
#define ll long long 
#define maxn 1000010
using namespace std; 
int sum[maxn]; 
int main(){
  int n,m;  cin>>n>>m;
  for(int i=1;i<=n;i++){
    int x;  cin>>x;
    sum[i]=sum[i-1]+x; 
  }
  while(m--){
    int l,r;  cin>>l>>r;
    cout<<sum[r]-sum[l-1]<<"\n"; 
  }
  return 0; 
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];//b数组为差分数组  a 数组是 b 数组的前缀和
int n,m;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]-a[i-1]; }
    while(m--){
        int l,r,c;  cin>>l>>r>>c;
        b[l]+=c; b[r+1]-=c;  //这里一定要记住 要给 b[r+1]减去 c ,
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b[i]; //求前缀和
        cout<<a[i]<<" ";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std; 
int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    string s;
    cin >> s;
    int n = s.length();
    bool is = true; //bool 类型的值只有 true 和 false
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) {
            is = false;
        }
    }
    cout << (is ? "Yes" : "No") << "\n";
    return 0;
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
int ans;//存结果 
//求  a的b次方 对 mode 求余的结果  即  (a^b)%mod 
//思路是将 b 转成二进制 
// 2^16次方  就是 2^8 * 2^8   ,2^8 就是 2^4 * 2^4  ... 
int quickPow(int a,int b,int mod){
  int res=1;
  while(b){
    if(b&1) res=res*a%mod;
    b>>=1;
    a=a*a%mod; 
  }
  return res; 
} 
int main(){
  int a,b,mod;
  cin>>a>>b>>mod;
  ans = quickPow(a,b,mod);
  cout<<ans; 
  return 0; 
}

struct Mat
{
    LL m[101][101];
};//存储结构体
Mat a,e; //a是输入的矩阵，e是输出的矩阵
Mat Mul(Mat x,Mat y)
{
    Mat c;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            c.m[i][j] = 0;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                c.m[i][j] = c.m[i][j]%mod + x.m[i][k]*y.m[k][j]%mod;
            }
        }
    }
    return c;
}
Mat pow(Mat x,LL y)//矩阵快速幂
{
    Mat ans = e;
    while(y){
        if(y&1) ans = Mul(ans,x);
        x = Mul(x,x);
        y>>=1;
    }
    return ans;
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
// 定理  gcd(a,b)*lcm(a,b) = a*b  
//最大公约数  求 a 与 b 的最大公约数 
int gcd(int a,int b){
  if(b==0) return a;
  return gcd(b,a%b);
}
//最小公倍数 
int lcm(int a,int b){
  return a*b/gcd(a,b); // 
} 
int main(){
  int a,b;
  cin>>a>>b;
  int ans1=gcd(a,b);
  int ans2=lcm(a,b);
  cout<<ans1; 
  cout<<"\n"; 
  cout<<ans2;
  return 0; 
}

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n;  cin>>n;
  if( (n%4==0&&n%100!=0) || n%400==0) cout<<"yes";
    else cout<<"no";
  return 0; 
}

int f(int x){ //判断 x 是不是质数  
  if(x==1) return 0;
  for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0;
  return 1;
}

#include<bits/stdc++.h>
using namespace std;
int a,b;
int prime[1000010];//存储质数
int ht[1000010];
struct tx{
  int x,y;
}c[20];
int ans[100];
int ct1=0;
int main(){
  ios::sync_with_stdio(false);
  cin>>a>>b;
  int ct=0;
  for(int i=2;i<=b;i++){//预处理质数
    if(!ht[i]){
      prime[ct++]=i;// 将质数加入到 数组中
      for(int j=i*i;j<b;j=j+i) ht[j]=true;  //将 改质数的倍数全部 标记为合数
    }
  }
  //分解质因数 
  for(int i=a;i<=b;i++){ //对 a  到 b 的每一数进行分解
    int t=i;
    int len=0;
    for(int j=0;j<ct;j++){ //这里是核心
      if(t%prime[j]==0){
        c[len].x=prime[j];
        c[len].y=0;
        while(t%prime[j]==0){
          c[len].y++;
          t/=prime[j];
        }
        len++;
      }
    }
    cout<<i<<"=";
    for(int j=0;j<len;j++){
      int t2 = c[j].y;
      for(int k=0;k<t2;k++){
        ans[ct1++]=c[j].x;
      }
    }
    for(int j=0;j<ct1;j++){
      if(j!=0) cout<<"*"; cout<<ans[j];
    }
    ct1=0;
    cout<<"\n";
//    memset(c,0,sizeof(c));
    memset(ans,0,sizeof(ans));
  }
    return 0;
}

#include<bits/stdc++.h>
#define ll long long 
#define maxn 2010 
using namespace std; 
int n;
int mod = 1e9+7;
int c[maxn][maxn];//和数学中的求组合一样， 表示几个中选几个的结果 
void init(){
  for(int i=0;i<=2000;i++){
    for(int j=0;j<=i;j++){
      if(!j) c[i][j]=1;
      else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
  }
} 
int main(){
  init(); 
  cin>>n;
  while(n--){
    int a,b;  cin>>a>>b;
    cout<<c[a][b]<<"\n";
  }
  return 0; 
}

class Solution {
public:
    int numTrees(int n) {
        long long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;
    }
};