https://ac.nowcoder.com/discuss/364961?tdsourcetag=s_pctim_aiomsg
题解传送门

本次比赛C题DP挺经典的，值得回顾。

G题判正误

判断 $图片说明$

最早觉得是大数，一开始想直接用python糊过去。pythonTLE了以后还搞了很久的大数快速幂/大数加法，最后还是ZT大佬提醒我数据范围1e9……
如果不取模直接快速幂也过不了。
这次比赛一个深刻的教训就是大数取模，浮点数eps，不管题目给没给，都要考虑。

cpp代码

多次取模快速幂

#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
//const int mod=1e9+7;
ll qkpow(ll x, ll y,int mod) {
    if(x==0) return 0;
    else if(y==0) return 1;
    ll ans = 1;
    x = x % mod;
    while (y) {
        if(y&1) ans = ans*x %mod;
        x = x*x %mod;
        y = y>>1;
    }
    return ans;
}
ll a,b,c,d,e,f,g;
bool check(int mod){
    ll ans1=qkpow(a,d,mod);
        ll ans2=qkpow(b,e,mod);
        ll ans3=qkpow(c,f,mod);
        if(g-ans1-ans2==ans3) return 1;
        else return 0;
}
int main() {
    int T;
    sscc;
    cin>>T;
    while(T--) {
        cin>>a>>b>>c>>d>>e>>f>>g;
        int flag=1;
        int mod=1e9+7;
        if(!check(mod)) flag=0;
        mod=1e9+11;
        if(!check(mod)) flag=0;
        mod=1e9+1;
        if(!check(mod)) flag=0;
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

多次取模来确保答案准确性，时间消耗会增加约40%不过离1s还是很远。

偷鸡的pow函数

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,a,b,c,d,e,f,g;
    cin>>n;
    while(n--){
        cin>>a>>b>>c>>d>>e>>f>>g;
        long long x=pow(a,d),y=pow(b,e),z=pow(c,f);
        if(x+y+z==g)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

还有一件事情就是要储备大数模板，其实模板这种东西最好是自己写，希望我之后有时间吧。

Python代码

爆锤弱数据代码

m=23456
n=int(input())
for _ in range(n):
      a,b,c,d,e,f,g=map(int,input().split())
      k=pow(a,d,m)+pow(b,e,m)+pow(c,f,m)
      if g%m==k%m:
            print('Yes')
            continue
      print('No')

这个是直接调用系统的库函数，但是我写的时候是这样写的：

a**d+b**e+c**f==g

然后就理所应当地超时了。
顺便吐槽这题数据不太正常。

顺便鞭尸一下我的python快速幂代码

def power(base,exponent):
    res = 1
    while exponent:
        if exponent & 1:
            res *= base
        base *= base
        exponent = exponent >> 1
    return res

n=int(input())
for i in range(n):
    a,b,c,d,e,f,g=map(int,input().split())
    g=g-power(c,f)
    g=g-power(b,e)
    if power(a,d) == g:
        print("Yes")
    else:
        print("No")

正确代码

t = int(input())
mods = (19270817, 10**9 + 7, 10**9 + 9)
for _ in range(t):
    a, b, c, d, e, f, g = map(int, input().split())
    flag = True
    for mod in mods:
        if (pow(a, d, mod) + pow(b, e, mod) + pow(c, f, mod)) % mod != g % mod:
            flag = False
            break
    print("Yes" if flag else "No")

不用取模的快速幂优化方案

def solve(x,n):
    res=1
    while n>0:
        if n&1:
            res=res * x
        if res>1000000000:
            break
        if res<-1000000000:
            break
        x=x*x
        n>>=1
    return res



t=int(input())
for i in range(t):
    a, b, c,d,e,f,g = map(int, input().split())
    cur1=0
    cur2=0
    cur3=0
    cur1=solve(a,d)
    cur2=solve(b, e)
    cur3=solve(c, f)
    if cur1+cur2+cur3==g:
        print("Yes")
    else:
        print("No")

E题做计数

求有多少个不同的正整数三元组 (i,j,k)满足 $图片说明$ ，且 $图片说明$ 。

两边平方后可化简得 $图片说明$
要使得 $图片说明$ 为整数，那么 $图片说明$ 必须是一个完全平方数。

for(ll i = 1; i*i<=n; i++)

所以枚举轮次这样写那么可以枚举ij的值。也就是因数个数，有多少个因数就有多少个i，就有多少个对应的j，加起来就可以了。

cpp代码

#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll f(ll n){
    ll s=1;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ll a=0;
            while(n%i==0){
                n/=i;
                a++;
            }
            s=s*(a+1);
        }
    }
    if(n>1) s=s*2;
    return s;
}
int main() {
    sscc;
    ll n,ans = 0,temp;
    cin>>n;
    for(ll i = 1; i*i<=n; i++)
        ans+=f(i*i);
    cout<<ans<<endl;
}

Python代码

n=int(input())
x=1
ans=0
while x*x<=n:
    i=1
    y=x*x
    while i*i<=y:
        if y%i==0:
            ans+=2
            if y==i*i:
                ans-=1
        i+=1
    x+=1
print(ans)

D题数三角

n个不重复点，有多少个钝角三角形。

这题我一开始用边长算超时了。ZT大佬指导又发现本菜鸡高中数学白学了，向量也写错了，太艰难了。
其实我想了很久辐角排序二分blabla，等有空再实现吧。那就是比较麻烦的计算几何了。

cpp代码

向量法

#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
string g;
struct po {
    int x,y;
} p[505];

inline bool check(int x,int y,int z){
    if((double)(p[x].x-p[z].x)*(p[x].y-p[y].y)==(double)(p[x].x-p[y].x)*(p[x].y-p[z].y)) return 0;
    if((p[x].x-p[z].x)*(p[y].x-p[z].x)+(p[x].y-p[z].y)*(p[y].y-p[z].y)<0) return 1;
    if((p[x].x-p[y].x)*(p[z].x-p[y].x)+(p[x].y-p[y].y)*(p[z].y-p[y].y)<0) return 1;
    if((p[y].x-p[x].x)*(p[z].x-p[x].x)+(p[y].y-p[x].y)*(p[z].y-p[x].y)<0) return 1;
    return 0;
}

int main() {
    scanf("%d",&n);
    for(int i=0; i<n; i++) 
        scanf("%d %d",&p[i].x,&p[i].y);
    ll cnt=0;
    for(int i=0; i<n; i++) 
        for(int j=i+1; j<n; j++) 
            for(int k=j+1; k<n; k++) 
                if(check(i,j,k)) cnt++;
    printf("%lld",cnt);
    return 0;
}

边长法

明天自己debug

向量算角

#include<bits/stdc++.h>
using namespace std;
const int N =1e4 + 50;
int x[N],y[N],n,ans;
int main(){
    cin >> n;
    for(int i =1; i<=n;i++) cin>> x[i]>> y[i];
    for(int i=1 ;i<=n;i++)
        for(int  j =1;j<=n;j++)
            for(int k=1;k<=n;k++){
                int x1 = x[j] - x[i],y1= y[j] -y[i];
                int x2 = x[k] - x[i],y2 = y[k] - y[i];
                if( x1*x2 + y1*y2 <0 && x1*y2- x2*y1!=0)
                    ans++;
            }
    cout<<ans/2<<endl;
    return 0;
}//CWR大佬的写法

双重循环明天看

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define test freopen("in","r",stdin);freopen("out","w",stdout);
#define inf 0x3f3f3f3f
const int maxn=505,mod=1e9+7;
struct nod {
    int x,y;
} p[maxn];
int n;
bool check(int a,int b,int c) {
    nod t1= {p[b].x-p[a].x,p[b].y-p[a].y};
    nod t2= {p[c].x-p[a].x,p[c].y-p[a].y};
    LL t=t1.x*t2.x+t1.y*t2.y;
    LL mo=1ll*(t1.x*t1.x+t1.y*t1.y)*(t2.x*t2.x+t2.y*t2.y);
    if(t<0&&t*t!=mo) return 1;
    return 0;
}
int main() {
    scanf("%d",&n);
    for(int i=0; i<n; ++i) scanf("%d%d",&p[i].x,&p[i].y);
    int ans=0;
    for(int i=0; i<n; ++i) 
        for(int j=0; j<n; ++j) 
            if(i!=j) for(int k=j+1; k<n; ++k) if(check(i,j,k)) ++ans;
    printf("%d",ans);
    return 0;
}

C题算概率

n道题，给出第1道到第n道做对的概率，求做对0到n道的概率。

青竹大佬的奇质数取模模板

#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qkpow(ll a, ll b) {
    ll ans = 1;
    a = a % mod;
    while (b) {
        if(b&1) ans = ans * a % mod;
        a = a * a % mod;
        b = b >>1;
    }
    return ans;
}
ll getInv(ll a) {
    return qkpow(a,mod-2);
}
int main() {
    ll x;
    while(cin>>x)
        cout<<getInv(x)<<endl;
    return 0;
}

思路

其实是没什么思路……
我一开始就是打算硬模拟，一个一个枚举计算，n<2000，怎么样都不可能超时。
比如n=3 已知p1 p2 p3，ans0=(1-p1)(1-p2)(1-p3)，这样的，然后后面就需要排列组合了。。
然后我遇到了一个困难：使用青竹大佬的模板可以把500000004和2互换，但是这是分子为1的情况，那万一概率是2/3，Inv(3)=333333336，输入就会是666666672，我怎么做到转换成概率分式呢？

三月回来复习这题，上面的话纯属胡思乱想。
这题的思路是DP，状态转移方程的含义就是：
前i题做出来j题的概率是前i-1题做出来j题的概率x第i题没做出来的概率+前i-1题做出来j-1题的概率x第i题做出来了的概率
b=mod+1-a意味着取模意义下的1-a，但是不能为负数故加上mod

cpp代码

#include <bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
long long ans[2005];
int main() {
    int n;
    scanf("%d",&n);
    ans[0]=1;
    for(int i=1; i<=n; i++) {
        ll a,b;
        scanf("%lld",&a);
        b=mod+1-a;
        for(int j=i; j>0; j--) ans[j]=(ans[j-1]*a+ans[j]*b)%mod;
        ans[0]=(ans[0]*b)%mod;
    }
    for(int i=0; i<=n; i++) printf("%lld ",ans[i]);
    return 0;
}

Python代码

mod = 1000000007
n = int(input())
p = [0] + list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1) :
    for j in range(i + 1) :
        dp[i][j] = (dp[i - 1][j] * (mod + 1 - p[i]) % mod + (dp[i - 1][j - 1] * p[i] % mod if j else 0)) % mod
print(' '.join(map(str, dp[n])))

寒假训练赛2 mod pow 数三角 dp inv

G题 判正误

判断

cpp代码

多次取模快速幂

偷鸡的pow函数

Python代码

爆锤弱数据代码

正确代码

不用取模的快速幂优化方案

E题 做计数

求有多少个不同的正整数三元组 (i,j,k)满足 ，且 。

cpp代码

Python代码

D题 数三角

n个不重复点，有多少个钝角三角形。

cpp代码

向量法

边长法

向量 算角

双重循环 明天看

C题 算概率

n道题，给出第1道到第n道做对的概率，求做对0到n道的概率。

青竹大佬的奇质数取模模板

思路

cpp代码

Python代码

G题判正误

判断 $图片说明$

E题做计数

求有多少个不同的正整数三元组 (i,j,k)满足 $图片说明$ ，且 $图片说明$ 。

D题数三角

向量算角

双重循环明天看

C题算概率