DYH
关于 文章 标签 分类 随想 导航 清单 时光 CS
DYH
/images/avatar.png

^_^

FFT & NTT

 发布于  收录于 Algorithm

前言

一篇没什么用的文章，记录一下FFT和NTT的板子

fft和ntt的原理参考FFT & NTT

概述

fft和ntt差不多，基础用法就是加速多项式乘法，把多项式从系数表示转成点值表示来方便计算，而要转成点值表示，不能选择任意点。有些点的若干次方是1（实际上可以是-1,+i,-i等等），这样不需要做所有的次方运算，而这些点在复平面单位圆上。在ntt中是拿原根替换fft的单位根。 它们的时间复杂度都是O(nlgn)

阅读全文
 Cpp, Number_theory

无聊的做题记录

 发布于  收录于 Problemlist

数学公式

题目

题解

错排公式

Dn = floor(n!/e + 0.5) = (n - 1) * (Dn-1 + Dn-2)

D1 = 0 , D2 = 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

//457ms/1000ms  488k/32768k
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll mod = 998244353;
int main() {
    ll n;
    cin >> n;
    ll one = 0, to = 1;
    ll ans = 0;
    for(int i = 2; i < n; ++i){
        ans = i * (one + to);
        ans %= mod;
        one = to;
        to = ans;
    }
    cout << ans ;
    return 0;
}

===============================================================

阅读全文
 Cpp, Problemlist

hhu_spider

 发布于  收录于 Python Web

hhu健康打卡脚本（返校版）

环境

必装环境 python， requests

推荐环境 anaconda, pycharm

功能说明

定时打卡、同时多人打卡、发邮件反馈打卡信息、失败重新打卡

（为什么不用发信息，国内手机号在twilio上不能用了）

阅读全文
 Python

Python爬虫

 发布于  收录于 Python Web

urllib模块

不使用

requests模块

获得网页源码

1
2
3
4

import requests
url = 'https://dyhgo.fun'
response = requests.get(url)
print(response.text)

带参数的url和UA伪装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#测试一下带参数的url和ua伪装
import requests
url = 'https://www.baidu.com/s'
name = input('输入您要搜索的内容，我们将返回百度搜索该信息的网页源码')
params = {
    'wd' : name
}
headers = {
    'User-Agent' : 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.89 Safari/537.36'
}
response = requests.get(url=url, params=params, headers=headers)
print(response.text)

案例：有道翻译查词

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#有道翻译的结果获取，查询look单词并将结果存储
import requests
import json
params = {
    'i': 'look',
    'from': 'AUTO',
    'to': 'AUTO',
    'smartresult': 'dict',
    'client': 'fanyideskweb',
    'salt': '16119129043609',
    'sign': '288cdf16af5fa68411381ba3c9f7f874',
    'lts': '1611912904360',
    'bv': '44a53b4124e8b822ebfd881c5a599938',
    'doctype': 'json',
    'version': '2.1',
    'keyfrom': 'fanyi.web',
    'action': 'FY_BY_REALTlME'
}
url = 'http://fanyi.youdao.com/translate_o?smartresult=dict&smartresult=rule'
headers = {
    'User-Agent' : 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.89 Safari/537.36'
}
response = requests.post(url=url, data=params, headers=headers)
f = open('look.json', 'w', encoding='utf-8')
json.dump(response.json(), fp=f, ensure_ascii=False)
f.close()
print(response.json())

案例：获取豆瓣影单

网站链接

阅读全文
 Python

abc173

 发布于  收录于 Abc

A - Payment

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h> 
using namespace std;
int main(){
	int n;
	cin>>n;
	int i=1000;
	while(i<n){
		i+=1000;
	}
	cout<<i-n;
	return 0;
}

B - Judge Status Summary

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include<bits/stdc++.h> 
using namespace std;
const int maxn = 1e5+2;
int wa,tle,ac,re;
int main(){
	int n;
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		switch(s[0]){
			case 'A':{
				ac++;
				break;
			}
			case 'W':{
				wa++;
				break;
			}
			case 'T':{
				tle++;
				break;
			}
			default:{
				re++;
				break;
			}
		}
	}
	cout<<"AC x "<<ac<<endl<<"WA x "<<wa<<endl<<"TLE x "<<tle<<endl<<"RE x "<<re<<endl;
	return 0;
}

C - H and V

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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

char a[7][7];
char b[7][7];
int n,m;int k;
void row(int x){
	for(int i=0;i<m;i++){
		b[x][i] = '.';
	}
}

void col(int x){
	for(int i=0;i<n;i++){
		b[i][x] = '.';
	}
}


void sol(int x,int y){
	for(int i=0;i<n;i++){
		if(x>>i&1){
			row(i);
		}
	}
	
	for(int j=0;j<m;j++){
		if(y>>j&1){
			col(j);
		}
	}
}

int cal(){
	int ans =0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(b[i][j] == '#') ans++;
		}
	}
	return ans;
}

int main(){
	cin>>n>>m;cin>>k;
	char c;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			
		}
	}
	int ans = 0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<m);j++){
			memcpy(b,a,sizeof(a));
			sol(i,j);
			if (cal() == k) ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

D - Chat in a Circle

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include<bits/stdc++.h> 
using namespace std;
using ll = long long;
ll a[200005];
ll n;
int main(){
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,[](int a,int b){return a>b;});
	if(n==2) {
		cout<<a[0]<<endl;
		exit(0);
	}
	n--;
	ll t;
	ll q = n;
	if(n&1){
		t = (n-1)/2;
		t++;
	}
	else{
		n++;
		t = (n-1)/2;
		t++; 
	}
	ll ans = a[0];
	for(ll i=1;i<t;i++){
		ans += 2LL * a[i];
	}
	if(q%2 == 0){
		ans -= a[t-1];
	}
	cout<<ans<<endl;
	return 0;
}

E - Multiplication 4

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll a[200005];
ll n,k;
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int L = 0,R = n-1;
	if(k&1){
		if(a[n-1] < 0){
			ll ans = 1;
			for(int i=n-1;i>=n-k;i--){
				ans *= a[i];
				ans %= mod;
			}
			if(ans < 0) cout<<ans+mod<<endl;else cout<<ans<<endl;
			exit(0);
		}
		
		R--,k--;
	}
	while(k){
		ll lv = a[L] * a[L+1];
		ll rv = a[R] * a[R-1];
		
		if(lv < rv){
			R -= 2;
		}	else L += 2;
		k -= 2;
	}
	ll ans = 1;
	for(int i=0;i<L;i++){
		ans *= a[i];
		ans %= mod;
	}
	for(int i=R+1;i<n;i++){
		ans *= a[i];
		ans %= mod;
	}
	if(ans < 0) cout<<ans+mod<<endl;
	else cout<<ans<<endl;
	return 0;
}

F - Intervals on Tree

题解

对于一个森林，点和边对连通图个数的贡献是每个点+1，每条边-1

阅读全文
 Cpp, Graph_theory

某不科学的暑假做题记录

 发布于  收录于 Problemlist

简单思维

题目

题解

直接法，注意数组大小爆long long

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using ll = long long;
const ll  mod = 1e6+3;
ll fac[mod+2];
int main(){
	fac[0] = 1LL;
	fac[1] = 1LL;
	for(ll i=2;i<mod+2;i++){
		fac[i] = i*fac[i-1];
		fac[i] %= mod;
	}
	ll n;
	while(std::cin>>n){
		if(n>=mod) puts("0");else
		std::cout<<fac[n]<<std::endl;
	}
	return 0;
}

===========================================================================================================

阅读全文
 Cpp, Problemlist

abc172

 发布于  收录于 Abc

A - Calc

题意

看题目

题解

1
2
3
4
5
6
7
8
9

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	int a;
	cin>>a;
	cout<<a+a*a+a*a*a<<endl;
	return 0;
}

B - Minor Change

题意

看题目

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	string s,t;
	cin>>s>>t;
	int ans = 0;
	for(int i=0;i<s.length();i++){
		if(s[i]!=t[i])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

C - Tsundoku

题意

看题目

阅读全文
 Cpp, Counting, Prefix, Bit

abc171

 发布于  收录于 Abc

A - αlphabet

题意

看题目

题解

1
2
3
4
5
6
7
8

#include<bits/stdc++.h>
using namespace std;
int main(){
	char a;
	cin>>a;
	if(isupper(a)) cout<<'A';else cout<<'a';
	return 0;
}

B - Mix Juice

题意

看题目

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int ans = 0;
	for(int i=0;i<k;i++) ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

C - One Quadrillion and One Dalmatians

题意

类似于十进制转26进制

阅读全文
 Cpp, Counting

Django学习

 发布于  收录于 Python Web

跟着django文档实现投票app

需求

  • 一个让人们查看和投票的公共站点。
  • 一个让你能添加、修改和删除投票的管理站点。

环境

  • ide： pycharm community（不支持Django代码自动补全）
  • 版本：django 2.1.1
  • 数据库：sqlite

创建项目

1

django-admin startproject mysite

生成的文件结构

阅读全文
 Python