题目 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;
}

二分查找用快排的思想最好是o(N),但最坏是o(N*N)————就是假设求最大但每次取最前的都是最小时间复杂的N平方