XDU暑期训练D1训练日志
第一天讲了组合数学和概率期望，懂了有一半。
下午的训练也没写出来多少题，就把我写出来的题做以总结。
A题 整数分解为2的次幂（求出组合总数）
这道是PPT的例题，大概思路是
当n为偶数时：
n的总数是由（n-1）的总数+（n/2）的总数组成；/*（n-1）的每种方案中添加1，
即是所有包含1的方案；剩下的方案同时/2即是（n/2）的情况.*/
当n为奇数时：
n的总数是（n-1）的总数；//因为只多了1，所以在（n-1）的每种方案中添加1即可.
代码如下:
#include<cstdio>
using namespace std;
const int N=1000000007;
const int M=1100000;
long long a[M];
long long f(long long n)
{
if(n<=1) return 1;
if(a[n]) return a[n];
if(n&1)
{
a[n]=f(n-1)%N;
return a[n];
}
a[n]=(f(n-1)%N+f(n>>1)%N)%N;
return a[n];
}
int main(){
long long n;
scanf("%lld",&n);
printf("%lld",f(n));
return 0;
}
注：来源 51Nod - 1383。
B题 Permutations
题意大概是：随意给出一个n的全排列，求出它要经过几次置换才能成为单位元。
大致如上图所示。
本题可以换一个思路来做，去找每一位的数的循环节有几个元素（如1-4-2-1，则1的循环节
有3个元素），最后求出它们的最小公倍数输出即可。
代码如下：
#include<stdio.h>
#include<string.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int a[1100],map[1100];
int main()
{
int n,ans=1;
scanf("%d",&n);
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int temp=a[i];
int count=1;
map[i]=1;
while(temp!=i&&!map[temp])
{
map[temp]=1;
temp=a[temp];
count++;
}
ans=lcm(ans,count);
}
printf("%dn",ans);
}
注：其实这一道题是关于置换群的基础题，来源poj 2369。
C题 Invoker
题意：c种颜色，n个小球的涂色问题，问有几种染色方案（经过旋转翻折可以相同的算是一种方案）
老实说这道题是一窍不通，抄了模板过的。
大概是分为旋转和翻折两种情况去判断。
代码如下：
#include<stdio.h>
typedef long long ll;
const ll mod=1000000007;
ll c,n;
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll pow(ll p,ll n)
{
ll ans=1;
while(n)
{
if(n&1) ans=ans*p%mod;
p=p*p%mod;
n/=2;
}
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0)
{
x=1;y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return d;
}
int main()
{
int t;
scanf("%d",&t);
int cas=1;
while(t--)
{
scanf("%lld%lld",&c,&n);
int ans=0;
for(ll i=1;i<=n;i++)
{
ans+=pow(c,gcd(n,i));
ans%=mod;
}
if(n&1) ans+=(n*pow(c,n/2+1))%mod;
else ans+=(n/2*pow(c,n/2+1))%mod+(n/2*pow(c,n/2)%mod)%mod;
ans%=mod;
ll x,y;
exgcd(2*n,mod,x,y);
x=(x+mod)%mod;
printf("Case #%d: %lldn",cas++,ans*x%mod);
}
}
I题： A * B Problem Plus HDU - 1402
这题就是模拟乘法，数据比较大，用了JAVA的大数类。
代码如下：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String args[])
{
String str1,str2;
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
str1=in.next();
str2=in.next();
BigInteger a=new BigInteger(str1);
BigInteger b=new BigInteger(str2);
System.out.println(a.multiply(b));
}
}
}
注：不得不说Java好强！
相关知识
XDU暑期训练D1训练日志
史密斯机训练日志
MMSegmentation笔记05：训练+日志可视化+测试集性能评估
益智玩具训练 狗狗训练 边境牧羊犬训练 分离焦虑症
暑期旅游旺季来临 宁波宠物寄养市场“火”力全开
【狗狗训练
宠物狗狗训练视频－深圳翔鹏宠物警犬训练学校－贵宾神级训练视频表演
萌宠训练篇: 胖乎乎萌宠仓鼠的日常翻身训练, 萌宠的训练从小做起
宁波挚友宠物训练，两只狗狗的日常训练视频13957429102
小狗驯养日志送泥
网址: XDU暑期训练D1训练日志 https://m.mcbbbk.com/newsview348513.html
| 上一篇: 16 tensorBorad 可 |
下一篇: 宠物养成日记单机下载 |
