题目https://www.acwing.com/problem/content/218/
那个错误代码交上去是内存超限
把那两行超长注释符的句子注释掉是finish，不超了
我很好奇c矩阵也就1e7的int不到也能内存超限？
我一开始以为是异或有问题但用c【1】【i】【j】也是内存超限
并且注释掉那两行后，下面的遍历c也没有问题，真是玄学

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
typedef double db;
typedef unsigned long long ull;
#define fi first
#define se second
#define pk push_back
#define mk make_pair

const ll N=1e5+10, M=40, mod=1e9+7, inf=0x3f3f3f3f3f3f3f3f, Max=5e4;
const int iinf=0x3f3f3f3f;
const ll seed=233, hashmod=1e9+7;//哈希
const db esp=1e-7;

int n, a[N], last0[N][M], last1[N][M], c[4][N][M];
bool att[N][M], b[N][M];
// int aaa[200][100005];


void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        for(int j=0;j<31;j++){
            b[i][j]=(a[i]>>j)&1;
        }
    }

    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            last0[i][j]=last0[i-1][j];
            last1[i][j]=last1[i-1][j];
            if(b[i][j])
                last1[i][j]=i;
            else
                last0[i][j]=i;
        }
    }

    for(int j=0;j<31;j++){
        int flag=0;
        for(int i=1;i<=n;i++){
            att[i][j]=flag;
            c[flag][i][j]=c[flag][i-1][j]+1;
            c[1][i][j]=c[1][i-1][j];//////////////////////////////
            // if(b[i][j]) flag=flag?0:1;////////////////////////
        }
    }

    double axor=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            int flag=att[i][j];
            if(b[i][j])
                axor+=1.0*(1<<j)*(c[flag][i][j]-1)*2/n/n,
                        axor+=1.0*(1<<j)/n/n;//ok
            else
                axor+=1.0*(1<<j)*c[flag^1][i][j]*2/n/n;
        }
    }
    printf("%.3f ",axor);

    db aand=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            if(b[i][j]==1)
                aand+=1.0*(1<<j)*(i-last0[i][j]-1)*2/n/n,
                        aand+=1.0*(1<<j)/n/n;
        }
    }
    printf("%.3f ",aand);

    db aor=0;
    for(int j=0;j<31;j++){
        for(int i=1;i<=n;i++){
            if(b[i][j]==1){
                aor+=1.0*(1<<j)*(i-1)*2/n/n;
                aor+=1.0*(1<<j)/n/n;
            }else{
                aor+=1.0*(1<<j)*(last1[i][j])*2/n/n;
            }
        }
//cout<<j<<" "<<(1<<j)<<"  "<<aand<<endl;
    }
    printf("%.3f",aor);

    return ;
}
int main() {
//     freopen("C:\\Users\\lenovo\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\lenovo\\Desktop\\out.txt","w",stdout);
//    ll t;
//    cin>>t;
//    for(ll i=1;i<=t;i++)
    work();

    return 0;
}

题目 ABC 171F （要梯子）
大意就是：给一个len长的小写字母字符串s，然后你可以随意的把26个小写字母插进s，直到s长n，求可以构成多少不同的长度为n的字符串
就只是问两个简单的问题：
这个怎么算？
为什么答案与串s内容无关，只有长度有关？
答案貌似是 ： sum(i=len~n) { C(n,i) 25^(n-i) }
需要注意的是：比如说off，可以是of _ f，也可以是off_ ,但直接的c的话又会有 offf，对于f插入会重复计算，第1个是插入和第2个是插入，第3个是插入都是算一个

同余方程ax+by=c mod m, 用exgcd(a,b,x,y)求得的x和y的范围怎么求？
https://codeforces.com/problemset/problem/1244/C
这道题目用exgcd求x,y暴ll了

听说Python好慢，运行时间好像是c的20多倍
但pypy好像还不错
两个问题求答：
1.请问pypy的语法和Python是一样的吗？（我看了下代码，貌似一样）
2.打acm的话好像可以用Python，那么这里的Python是Python3还是pypy3呢？

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    stringstream s;
    s.precision(0);
    s<<fixed<<pow(2.0L,n+1);  //将pow后存进去
    string a=s.str();    //放到a中，这里个位数只能是2,4,8,6
    a[a.length()-1]--;
    a[a.length()-1]--;   //减去2，不会影响上一行
    cout<<a<<endl;
    return 0;
}

这两句什么意思

s.precision(0);
s<<fixed<<pow(2.0L,n+1);

另外有没有大佬知道关于stringstream在算法竞赛中应用的较详细博客

for(auto i:se)的i是什么

set<int> se;
for(auto i:se){
        if(*i!=se.begin()) cout<<" ";
        cout<<i; 
    }

上面报错，主要是刷pta的时候要求末尾不能有多余的空格，
所以用auto的时候就不知道怎么判断当前是不是第一个（即begin（））
正常是数组的时候是这样的

for(int i=0;i<n;i++){
    if(i).......
    cout<<.........
}

所以这里问下for(auto i:se)怎么判断现在是第一次遍历或者判i是不是se的begin

https://www.acwing.com/problem/content/225/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e3+10;
int n;
ll a[N],b[N],M,m[N],infm[N],y,ans;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    M=1;
    for(int i=0;i<n;i++) M*=a[i];
    for(int i=0;i<n;i++) m[i]=M/a[i],exgcd(m[i],a[i],infm[i],y);
    for(int i=0;i<n;i++) ans=(ans+b[i]*m[i]*infm[i])%M;
    cout<<(ans%M+M)%M<<endl;
    return 0;
}

这里exgcd(m[i],a[i],infm[i],y)是求m【i】的逆
就是
m*m^-1=1（mod a）
=> m * m^-1=1+ y * a
=> m * m^-1 - a * y=1
为什么exgcd(m[i],-a[i],infm[i],y); 的答案是错的？

(a * b * c)/d%MOD
abc%d==0
现在已知ab在longlong范围内，但ab*c/d会爆longlong,怎么把%MOD放到前面，如果可以能不能写下证明

(另类的扩展欧几里得)

直接上代码了（纯属学术交流，不建议实战）

#include<bits/stdc++.h>
using namespace std;

int n,a,b,x,y;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int tmp=y;
    y=x-a/b*y;
    x=tmp;
    return d;
}

int main(){
    cin>>n;
    while(n--){
        x=y=0;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

dp相对于暴力优化了什么
就比如：输入一个数n，求n分解成质数相加方法数，如：7=7=2+5=2+2+3，方法数为3
我想的暴力是：
先线性求出1~n的质数
然后递归遍历相加质数直到sum>=n

然而dp是dp【i】=dp【i】+dp【i-质数】

dp优化了什么？为什么dp用的时间少，他们两个不是都考虑了所有情况吗

暴力代码：

#include <iostream>

using namespace std;

int cnt,n,ans;
int prime[1005];
bool st[1005];

void work(int sum,int no){
    if(sum==n) {
        ans++;return;
    }
    else if(sum>n) return;
    for(int i=no;prime[i]+sum<=n&&i<cnt;i++){
        work(prime[i]+sum,i);
//printf("%d\n",prime[i]+sum);      
    }

}
int main(int argc, char** argv) {
    cin>>n;

    for(int i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }

//  puts("this");

    work(0,0);
    cout<<ans;
    return 0;
}