5102

yut2020
junjun

castlecaffe
IndexYang
j5zslhw

Dream_56

hei103

RyanMoriarty
bobo2010

ByteTV
zombotany

1天前
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

//const int N =  + 10;
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = (ll)res * t % p;
t = (ll)t * t % p;
k >>= 1;
}
return res;
}
ll x, n;
ll mod = 233333;
void solve() {
cin >> x >> n;
cout << qmi(x, n, mod);
}

int main() {

ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

int T = 1;
//  cin >> T;
while(T -- ) {
solve();
}
return 0;
}



14天前
最短路径中会包含重复点吗 就是一个点经过了两次



4个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];
int v[N], w[N];
int n, m;

int main()
{
cin >> n >> m;

for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

for(int i = n; i >= 1; i--) {
for(int j = 0; j <= m; j++) {
f[i][j] = f[i + 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}

int d = m;
for(int i = 1; i <= n; i++) {
if(d >= v[i] && f[i][d] == f[i + 1][d - v[i]] + w[i]) {
cout << i << " ";
d -= v[i];
}
}

return 0;
}



4个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n, m, root;
int h[N], e[N], ne[N], idx;
int w[N], v[N];
int f[N][N];

void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {

for(int i = h[u]; ~i; i = ne[i]) {
int son = e[i];
dfs(son);
for(int j = m - v[u]; j >= 0; j--) {
for(int k = 0; k <= j; k++) {
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
}
}
for(int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
for(int i = 0; i < v[u]; i++) f[u][i] = 0;

}

int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
v[i] = a, w[i] = b;
if(c == -1) root = i;
}

dfs(root);

cout << f[root][m];

return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << 12;
// 表示当前是第i列, 且第i列的状态是j的集合
// 1表示当前列需要填格子, 0表示不需要
long long f[N][M];
bool st[M];
int n, m;

int main() {

while(cin >> n >> m) {
if(!n && !m) break;
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 0; i < 1 << n; i++) {
st[i] = true;
int cnt = 0;
for(int j = 0; j < n; j++) {
if(i >> j & 1) {
if(cnt & 1) st[i] = false;
cnt = 0;
}else cnt++;
}
if(cnt & 1) st[i] = false;
}

// 从0到m-1
for(int i = 1; i <= m; i++) {
for(int j = 0; j < 1 << n; j++) {   // 枚举第i列的放法
for(int k = 0; k < 1 << n; k++) {   // 枚举i-1列的放法
if((j & k) == 0 && st[j | k]) {
f[i][j] += f[i - 1][k];
}
}
}
}
cout << f[m][0] << endl;
}

return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n;
char s[55];
int ne[55];
int f[55][55];
// kmp + 状态机DP 用kmp的匹配长度来当状态的点
int main() {
cin >> n;
cin >> s + 1;
int m = strlen(s + 1);
for(int i = 2, j = 0; i <= m; i++) {
while(j && s[j + 1] != s[i]) j = ne[j];
if(s[j + 1] == s[i]) j ++;
ne[i] = j;
}

f[0][0] = 1;
// 从前i个字符中 且当前已经匹配了长度为j的集合
for(int i = 1; i <= n; i++) {
for(int j = 0; j < m; j++) {
// 枚举第i个字符是多少
for(char c = 'a'; c <= 'z'; c++) {
int u = j;
while(u && c != s[u + 1]) u = ne[u];
if(c == s[u + 1]) u++;
if(u < m) {
f[i][u] = (f[i][u] + f[i - 1][j]) % mod;
}
}
}
}

int ans = 0;
for(int i = 0; i < m; i++) {
ans = (ans + f[n][i]) % mod;
}
cout << ans << endl;

return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;

int n;
int a[305];
int f[305][305];
int sum[305];
// 把第i堆到第j堆合并成一堆的集合 最小值
// 集合划分以最后一次合并的下标划分 (从i到j-1)
int main() {
memset(f, 0x3f, sizeof f);
cin >> n;
for(int i = 0; i <= n; i++) f[i][i] = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
for(int len = 1; len <= n; len++) {
for(int l = 1; l < n; l++) {
int j = l + len - 1;
if(j > n) continue;
for(int k = l; k <= j - 1; k++) {
f[l][j] = min(f[l][j], f[l][k] + f[k + 1][j] + sum[j] - sum[l - 1]);
}
}
}
cout << f[1][n];
return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 21000;
int f[N];
int idx;
int n, m;
int v[N], w[N];
// 二进制优化(二进制拼凑) 然后 01背包
int main() {

cin >> n >> m;
for(int i = 1; i <= n; i++) {
int V, W, S;
cin >> V >> W >> S;
int t = 1;
while(S >= t) {
v[++idx] = t * V;
w[idx] = t * W;
S -= t;
t = t * 2;
}
if(S) {
v[++idx] = S * V;
w[idx] = S * W;
}
}

for(int i = 1; i <= idx; i++) {
for(int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}

cout << f[m];

return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;

int f[1010];
int n, m;
int v, w;
int main() {

cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v >> w;
for(int j = v; j <= m; j++) {
f[j] = max(f[j - v] + w, f[j]);
}
}

cout << f[m];

return 0;
}



4个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n;
int primes[N], idx;
bool st[N];
vector<int> ve;
void oula(int x) {
for(int i = 2; i <= x; i++) {
if(!st[i]) primes[idx++] = i;
for(int j = 0; primes[j] <= x / i; j++) {
st[i * primes[j]] = true;
if(i % primes[j] == 0) break;
}
}
}
bool isPrime(int x) {
for(int i = 2; i <= x / i; i++)
if(x % i == 0) return false;
return true;
}

void dfs(int u, int ans, int num) {

if(num == 1) {
ve.push_back(ans);
return;
}

if(num - 1 > (u ? primes[u-1] : 0) && isPrime(num - 1)) {
ve.push_back(ans * (num - 1));
}

for(int i = u; primes[i] <= num / primes[i]; i++) {
int p = primes[i];
for(int j = 1+p, t = p; j <= num; t = t * p, j = j + t) {
if(num % j == 0) {
dfs(i + 1, ans * t, num / j);
}
}
}

}

int main() {
oula(N - 1);

while(cin >> n) {
ve.clear();
dfs(0, 1, n);

cout << ve.size() << endl;
sort(ve.begin(), ve.end());
if(ve.size()) {
for(int i = 0; i < ve.size(); i++) cout << ve[i] << " ";
cout << endl;
}

}

return 0;
}