题目来自 ICPC2017 Urumqi
最优的策略一定是：当有至少k 枚硬币面朝下时，则选k 枚面朝下的硬币去抛掷（任意k 枚都可以）；如果不足k枚面朝下，则在选择所有面朝下的硬币的基础上再额外选择若干面朝上的银币。
于是有动态规划，记F[i][j]表示抛掷了i 次后，有j 枚硬币面朝上的概率。他们应该满足F[i][0]+F[i][1]+...+F[i][n]=1。转移时，考虑从当前状态(i,j)出发，抛掷的k 枚硬币的所有可能结果：分别有0~k 枚面朝上。其中k 枚硬币抛掷后有l 枚面朝上的概率为C(k,l)/2k。时间复杂度O(nmk)。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int MAX=1000; 6 ll qmod(ll a,ll b) 7 { 8 ll ans=1; 9 while(b) 10 { 11 if(b&1) ans=ans*a; 12 a*=a; 13 b>>=1; 14 } 15 return ans; 16 } 17 double c[200][200],p[200]; 18 void init() 19 { 20 c[0][0]=1; 21 for(int i=1;i<106;i++) 22 { 23 c[i][0]=1; 24 for(int j=1;j<=i;j++) 25 c[i][j]=c[i-1][j-1]+c[i-1][j]; 26 } 27 p[0]=1; 28 for(int i=1;i<=106;i++) 29 p[i]=p[i-1]/2; 30 } 31 int main() 32 { 33 int T,n,m,t; 34 init(); 35 for(scanf("%d",&T);T;T--) 36 { 37 scanf("%d%d%d",&n,&m,&t); 38 double dp[200][200]; 39 memset(dp,0,sizeof(dp)); 40 dp[0][0]=1; 41 for(int i=0;i<m;i++) 42 { 43 for(int j=0;j<=n;j++) 44 { 45 if(dp[i][j]==0) continue; 46 for(int k=0;k<=t;k++) 47 { 48 if(n-j>=t) dp[i+1][j+k]+=dp[i][j]*c[t][k]*p[t]; 49 else dp[i+1][j-(t-(n-j))+k]+=dp[i][j]*c[t][k]*p[t]; 50 } 51 } 52 } 53 double ans=0; 54 for(int i=1;i<=n;i++) 55 ans+=dp[m][i]*i; 56 printf("%.3lf ",ans); 57 } 58 return 0; 59 }
四个数A1、A2、A3、A4。从小到大排序后输出A3*A4-A1*A2即可
在一个圆内有n个点，求连接任意两个点后，最多形成的区域数
最优的策略是在选定n个点后，两两连线，且满足任意三条线不交于一点。
本题需要用到欧拉公式：在平面图中，F=E-V+2，其中V是所有顶点数，E是边数，F是面数。（注意，本题需要减去外面的“无线面”）
任意四个点，会形成一个交点，并贡献额外的2条独立线段。所以V=n+C(n,4), E=n+2C(n,4)+C(n,2). （n是n段圆弧，2C(n,4)是一个交点所贡献的额外的2条独立线段，C(n,2)是n个点所能形成的边的个数），所以F=C(n,2)+C(n,4)+1.
本题的数据给的是1e18，所以对于取模运算要特别小心，防止超出longlong
1 #include <iostream> 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const ll mod=1e9+7; 6 ll extend_gcd(ll a, ll b, ll &x, ll &y) 7 { 8 if (b == 0) 9 { 10 x = 1, y = 0; 11 return a; 12 } 13 else 14 { 15 ll r = extend_gcd(b, a % b, y, x); 16 y -= x * (a / b); 17 return r; 18 } 19 } 20 ll inv(ll a, ll n)//求逆元 21 { 22 ll x, y; 23 extend_gcd(a, n, x, y); 24 x = (x % n + n) % n; 25 return x; 26 } 27 int main() 28 { 29 int t; 30 ll n; 31 scanf("%d",&t); 32 for(int cas=1; cas<=t; cas++) 33 { 34 scanf("%lld",&n); 35 if(n==1||n==2) 36 { 37 printf("Case #%d: %lld ",cas,n); 38 continue; 39 } 40 if(n==3) 41 { 42 printf("Case #%d: %lld ",cas,n+1); 43 continue; 44 } 45 ll b1=n%mod,b2=(n-1)%mod,b3=(n-2)%mod,b4=(n-3)%mod;//特别注意取模 46 ll a2=(b1*b2)%mod; 47 ll a3=(a2*b3)%mod; 48 ll a4=(a3*b4)%mod; 49 ll n4=(a4%mod*inv(24,mod)%mod)%mod; 50 ll n2=(a2%mod*inv(2,mod)%mod)%mod; 51 ll ans=n4+n2+1+mod; 52 ans%=mod; 53 printf("Case #%d: %lld ",cas,ans); 54 } 55 return 0; 56 }
给你一连串的点的坐标，保证x1<x2<...<xn,y1=0,yn=0 求这些坐标依次连线后与x轴所围成的面积，首先先求一下第一个和最后一个三角形，再依次求中间的梯形的面积。
记F[i]表示数位和为i 的不含0 整数有多少个，再记G[i]表示数位和为i 的不含0 整数的和。那么F[i] = sum F[i-j]、G[i] = sum 10G[i-j]+jF[i-j]，其中j 枚举了最低位的数字，并从1 遍历到9。
不妨同时维护相邻的9 个位置的值（共18 个），则可以构造18 阶矩阵A，实现它的快速转移。整个问题的答案也对应了A 的ab 次幂。可以利用矩阵乘法的结合律实现它的快速计算。
参考https://www.cnblogs.com/tian-luo/p/9515011.html
可以用_int128来存储ab，关键是要能想到构造矩阵，该构造什么样的矩阵
1 #include <iostream> 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 ll p=1e9+7; 6 int add(int a,int b) //加法取模 7 { 8 return a+b>=p?a+b-p:a+b; 9 } 10 int mul(ll a,int b) //乘法取模 11 { 12 return a*b%p; 13 } 14 struct Mat //定义矩阵 15 { 16 int v[18][18]; 17 Mat() 18 { 19 memset(v,0,sizeof(v)); 20 } 21 void init() //单位矩阵 22 { 23 for(int i=0;i<18;i++) 24 { 25 v[i][i]=1; 26 } 27 } 28 }; 29 Mat operator *(Mat x,Mat y) 30 { 31 Mat z; 32 for(int i=0;i<18;i++) //新的写法，节省计算0的时间 33 { 34 for(int j=0;j<18;j++) 35 { 36 if(x.v[i][j]) 37 { 38 for(int k=0;k<18;k++) 39 { 40 if(y.v[j][k]) 41 { 42 z.v[i][k]=add(z.v[i][k],mul(x.v[i][j]%p,y.v[j][k]%p)); 43 } 44 } 45 } 46 } 47 } 48 return z; 49 } 50 Mat Matqmod(Mat a,__int128 b) //矩阵快速幂 51 { 52 Mat c; 53 c.init(); 54 while(b) 55 { 56 if(b&1) 57 { 58 c=c*a; 59 } 60 a=a*a; 61 b>>=1; 62 } 63 return c; 64 } 65 int main() 66 { 67 ll cnt[15]={0},sum[15]={0}; 68 cnt[0]=1; 69 for(int i=1;i<=9;i++) //初始化1~9的cnt[]和sum[] 70 { 71 for(int j=1;j<=i;j++) 72 { 73 cnt[i]+=cnt[i-j]; 74 sum[i]+=10*sum[i-j]+j*cnt[i-j]; 75 } 76 } 77 Mat a,b; 78 a.v[0][0]=10; 79 for(int i=1;i<9;i++) //构造矩阵 a 80 { 81 a.v[0][i]=10; 82 a.v[i][i-1]=1; 83 } 84 for(int i=9;i<18;i++) 85 { 86 a.v[0][i]=i-8; 87 a.v[9][i]=1; 88 } 89 for(int i=10;i<18;i++) 90 { 91 a.v[i][i-1]=1; 92 } 93 94 int t; 95 scanf("%d",&t); 96 while(t--) 97 { 98 ll n,m; 99 scanf("%lld %lld %lld",&n,&m,&p); 100 for(int i=0;i<9;i++) //构造矩阵 b 101 { 102 b.v[i][0]=sum[9-i]%p; 103 } 104 for(int i=9;i<18;i++) 105 { 106 b.v[i][0]=cnt[18-i]%p; 107 } 108 __int128 now=n; 109 for(int i=2;i<=m;i++) //用_int128计算a的b次方 110 { 111 now=now*(__int128)n; 112 } 113 if(now<=9) //now<=9直接输出 114 { 115 printf("%lld ",sum[now]%p); 116 continue; 117 } 118 Mat c=Matqmod(a,now-9)*b; //now>9 套用矩阵 119 printf("%lld ",c.v[0][0]); 120 } 121 return 0; 122 } 123
带权并查集 参考https://blog.csdn.net/mitsuha_/article/details/80418507
有一棵树，首先给你c个关系，每个关系表示u和v之间的异或和为val，问你在这个关系中，从第一个开始依次往下最多能同时满足多少个。
记r[i]为节点i到根的路径上所有边的异或和，则每一个关系中实际上给出了r[u]xorx[v]的值
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int MAX=1e5+10; 6 int fa[MAX],n,c,t; 7 ll r[MAX]; 8 void init() 9 { 10 for(int i=0;i<=n;i++) 11 fa[i]=i,r[i]=0; 12 } 13 int Get(int x) 14 { 15 if(x==fa[x]) return x; 16 int fx=fa[x]; 17 fa[x]=Get(fa[x]); 18 r[x]^=r[fx]; 19 return fa[x]; 20 } 21 int main() 22 { 23 // freopen("in.txt","r",stdin); 24 for(scanf("%d",&t);t;t--) 25 { 26 scanf("%d%d",&n,&c); 27 int a,b; 28 for(int i=1;i<n;i++) 29 scanf("%d%d",&a,&b); 30 init(); 31 int ans=c+1; //这里要令ans=c+1 32 int x,y; 33 ll z; 34 for(int i=1;i<=c;i++) 35 { 36 scanf("%d%d%lld",&x,&y,&z); 37 if(ans!=c+1) continue; 38 int fx=Get(x),fy=Get(y); 39 if(fx==fy&&(r[x]^r[y])!=z) ans=i; 40 else 41 { 42 fa[fx]=fy; 43 r[fx]=r[x]^r[y]^z; 44 } 45 } 46 printf("%d ",ans-1); //这里注意是ans-1 47 } 48 return 0; 49 }
参考https://blog.csdn.net/hao_zong_yin/article/details/81613218
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int MAX=1e4+10; 5 const int mod=998244353; 6 typedef long long ll; 7 ll qmod(ll a,ll b) //快速幂，后面求逆元的时候会用到 8 { 9 ll ans=1; 10 while(b) 11 { 12 if(b&1) ans=(ans*a)%mod; 13 a=a*a%mod; 14 b>>=1; 15 } 16 return ans; 17 } 18 bool is_prime[MAX]; //判断是不是质数 19 int prime[MAX],prime_cnt; //prime[]用来存储质数，prime_cnt表示质数的个数 20 void getPrime() //素数筛 21 { 22 prime_cnt=0; 23 is_prime[0]=is_prime[1]=1; 24 for(int i=2;i<MAX;i++) 25 { 26 if(!is_prime[i]) 27 { 28 prime[prime_cnt++]=i; 29 for(int j=2;j*i<MAX;j++) 30 is_prime[j*i]=1; 31 } 32 } 33 } 34 int t,k,get_p[50]; //get_p[]存储分解的质因数 35 int main() 36 { 37 getPrime(); 38 for(scanf("%d",&t);t;t--) 39 { 40 scanf("%d",&k); 41 int n=k; 42 ll sum=(ll)k%mod*(k+1)%mod*(2*k+1)%mod*qmod(6,mod-2)%mod%mod; //所有数的平方和 43 int p_cnt=0; 44 for(int i=0;i<prime_cnt;i++) 45 { 46 if(prime[i]>n) break; 47 if(k%prime[i]==0) //分解质因数 48 { 49 get_p[p_cnt++]=prime[i]; 50 while(k%prime[i]==0) k/=prime[i]; 51 } 52 } 53 if(k>1) get_p[p_cnt++]=k; 54 ll ans=0; 55 for(int i=1;i<(1<<p_cnt);i++) //利用二进制进行容斥 56 { 57 ll x=1; 58 int cnt=0; 59 for(int j=0;j<p_cnt;j++) 60 { 61 if((i>>j)&1) 62 { 63 x=x*get_p[j]%mod; 64 cnt++; 65 } 66 } 67 k=n/x; 68 if(cnt&1) ans=(ans+(ll)x*x%mod*k%mod*(k+1)%mod*(2*k+1)%mod*qmod(6,mod-2)%mod)%mod; //奇数个相加 69 else ans=((ans-(ll)x*x%mod*k%mod*(k+1)%mod*(2*k+1)%mod*qmod(6,mod-2)%mod)%mod+mod)%mod; //偶数个相减 70 } 71 ans=((sum-ans)%mod+mod)%mod; //减去不合法的，即为最终合法的 72 printf("%lld ",ans); 73 } 74 return 0; 75 }