A Eddy Walker
题目描述
有一个0到n-1的环,起点从0开始,每次可以向前或向后走一格,当一个格子被第二次走到,就停止。求出走到m的概率。输出对答案取模1e9+7。
1≤T≤1021
0≤Mi<Ni≤1e9
样例
输入:
3
1 0
2 1
3 0
输出:
1
1
0
知识点(逆元,快速幂)
当n=1时,只有0一个点,所有只能走到0,概率为1;当m=0时,不会停在0,所以概率时0;其他情况,除了0,停在其他格子的概率为
2/(2*(n-1))=1/(n-1) 即 inv(n-1)
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <math.h>
#include <set>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
#define fori(a, b) for (int i = (a); i < (b); i++)
#define forj(a, b) for (int j = (a); j < (b); j++)
#define fork(a, b) for (int k = (a); k < (b); k++)
#define DR freopen("P1182_5.in", "r", stdin);freopen("P1182_5.out", "w", stdout)
void nextLine(){printf("\n");}
void inIntArray(int *p, int n){for (int i = 0; i < n; i++){scanf("%d", &p[i]);}}
void outIntArray(int *p, int n){for (int i = 0; i < n; i++){printf("%d ", p[i]);}nextLine();}
int ri(){int n;scanf("%d", &n);return n;}
ll llri(){ll n;scanf("%lld", &n);return n;}
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
const ll mod = 1e9 + 7;
//快速幂板子
ll qpow(ll x, ll m)
{
ll ans = 1;
while(m){
if(m & 1){
ans = ans * x % mod;
}
x = x * x % mod;
m = m >> 1;
}
return ans;
}
ll ans = 1;
void solve(){
ll n = llri();
ll m = llri();
ll tp;
if(n==1&&m==0) tp=1;
else if(n>1&&m==0) tp=0;
else if(n>1&&m>0) tp=qpow(n-1,mod-2);
ans*=tp;
ans%=mod;
cout<<ans<<"\n";
}
int main()
{
//DR;
int roundTime = 1;
roundTime = ri();
while (roundTime--)
{
solve();
}
//cout<<ans<<endl;
}
F Partition problem
题目描述
有2n个人,给出一个二维数组,如果第i个和第j个人在同一个队伍里,队伍总体竞争值就加上Vij,求出总体竞争值的最大值。
样例
输入:
1
0 3
3 0
输出:
3
知识点(dfs)
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <math.h>
#include <set>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
#define fori(a, b) for (int i = (a); i < (b); i++)
#define forj(a, b) for (int j = (a); j < (b); j++)
#define fork(a, b) for (int k = (a); k < (b); k++)
#define DR freopen("P1182_5.in", "r", stdin);freopen("P1182_5.out", "w", stdout)
void nextLine(){printf("\n");}
void inIntArray(int *p, int n){for (int i = 0; i < n; i++){scanf("%d", &p[i]);}}
void outIntArray(int *p, int n){for (int i = 0; i < n; i++){printf("%d ", p[i]);}nextLine();}
int ri(){int n;scanf("%d", &n);return n;}
ll llri(){ll n;scanf("%lld", &n);return n;}
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
const ll mod = 1e9 + 7;
ll mp[505][505];
ll g1[505];
ll g2[505];
ll at = 0,bt = 0;
ll ans = 0;
ll m;
void dfs(ll pos,ll res){
if(pos>= 2*m){
ans = max(res,ans);
return;
}
if(at<m){
g1[++at] = pos;
ll tp = 0;
for (int i = 1; i <= bt; ++i) {
tp += mp[pos][g2[i]];
}
dfs(pos+1,res+tp);
at--;
}
if(bt<m){
g2[++bt] = pos;
ll tp = 0;
for (int i = 1; i <= at; ++i) {
tp += mp[pos][g1[i]];
}
dfs(pos+1,res+tp);
bt--;
}
}
void solve(){
m = llri();
for (int i = 0; i < m*2; ++i) {
for (int j = 0; j < m*2; ++j) {
mp[i][j] = llri();
}
}
dfs(0,0);
cout<<ans<<"\n";
}
int main()
{
//DR;
int roundTime = 1;
//roundTime = ri();
while (roundTime--)
{
solve();
}
//cout<<ans<<endl;
}
赞!