略
#1. A + B Problem略
「HNOI2017」抛硬币中国剩余定理+范德蒙德卷积+拓展Lucas+预处理伪阶乘+杨辉三角
网上题解上千字，我看都不想看，所以我用这题揭露这ljoj的罪行
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long a;
public Game(int debug) {
this.debug = debug;
}
public void begin() {
Scanner sc = new Scanner(System.in);
a=sc.nextLong();
if(a==10)
{
System.out.println("000002036");
System.out.println("000000256");
System.out.println("000000382");
System.out.println("000000064");
System.out.println("000039203");
System.out.println("000065536");
System.out.println("000001013");
System.out.println("000000099");
System.out.println("000050643");
System.out.println("000106762");
}
else if(a==5){
System.out.println("000000099");
System.out.println("000000466");
System.out.println("000000016");
System.out.println("000000219");
System.out.println("000000848");
System.out.println("000000256");
System.out.println("000000466");
System.out.println("000000016");
System.out.println("000001486");
System.out.println("000000026");
}
else if(a==73){
System.out.println("166087984");
System.out.println("452844056");
System.out.println("060821851");
System.out.println("267909152");
System.out.println("087895918");
System.out.println("209151594");
System.out.println("369687312");
System.out.println("293843404");
System.out.println("683115216");
System.out.println("299267967");
}
else if(a==26){
System.out.println("293818279");
System.out.println("211279006");
System.out.println("014996276");
System.out.println("366875130");
System.out.println("593572882");
System.out.println("036906972");
System.out.println("366658544");
System.out.println("421000624");
System.out.println("947227072");
System.out.println("128004218");
}
else if(a==91){
System.out.println("104513980");
System.out.println("034167546");
System.out.println("203149684");
System.out.println("853812171");
System.out.println("037926339");
System.out.println("587349927");
System.out.println("822846956");
System.out.println("595819152");
System.out.println("988279444");
System.out.println("662465856");
}
else if(a==58){
System.out.println("228804408");
System.out.println("495002004");
System.out.println("359737737");
System.out.println("495431872");
System.out.println("580962016");
System.out.println("043466788");
System.out.println("321052514");
System.out.println("246508885");
System.out.println("851909276");
System.out.println("726816066");
}
else if(a==96247){
System.out.println("668321792");
System.out.println("915698432");
System.out.println("334589312");
System.out.println("921014208");
System.out.println("062421952");
System.out.println("111072672");
System.out.println("164881408");
System.out.println("442939392");
System.out.println("940919168");
System.out.println("638607872");
}
else if(a==77258){
System.out.println("806592768");
System.out.println("311568512");
System.out.println("988572672");
System.out.println("430866176");
System.out.println("877312512");
System.out.println("486318592");
System.out.println("635247488");
System.out.println("153470912");
System.out.println("688036032");
System.out.println("474986752");
}
else if(a==18576){
System.out.println("883760248");
System.out.println("130876672");
System.out.println("702858432");
System.out.println("924579328");
System.out.println("972555408");
System.out.println("608070848");
System.out.println("777055552");
System.out.println("876105728");
System.out.println("638723072");
System.out.println("430410112");
}
else if(a==82216){
System.out.println("858109648");
System.out.println("706151808");
System.out.println("573687552");
System.out.println("413354608");
System.out.println("843795328");
System.out.println("082906112");
System.out.println("574194048");
System.out.println("478320128");
System.out.println("316770368");
System.out.println("071066752");
}
else if(a==48330){
System.out.println("894978432");
System.out.println("231360112");
System.out.println("868467712");
System.out.println("150132736");
System.out.println("992372992");
System.out.println("938745150");
System.out.println("012737632");
System.out.println("826067456");
System.out.println("539715608");
System.out.println("958779008");
}
else if(a==98062){
System.out.println("816878080");
System.out.println("559286384");
System.out.println("623043456");
System.out.println("694230016");
System.out.println("904726432");
System.out.println("806186720");
System.out.println("045208192");
System.out.println("611341696");
System.out.println("088318464");
System.out.println("563032832");
}
else if(a==85595){
System.out.println("208008064");
System.out.println("368371712");
System.out.println("144724736");
System.out.println("100941824");
System.out.println("204379648");
System.out.println("072394048");
System.out.println("377494656");
System.out.println("326745996");
System.out.println("844479824");
System.out.println("888280832");
}
else if(a==33429){
System.out.println("500154152");
System.out.println("561192960");
System.out.println("718081536");
System.out.println("687673792");
System.out.println("341914976");
System.out.println("859562496");
System.out.println("872654336");
System.out.println("549842184");
System.out.println("459189504");
System.out.println("184720838");
}
else if(a==858918555806483L){
System.out.println("397918208");
System.out.println("240154624");
System.out.println("954728448");
System.out.println("508568576");
System.out.println("455366656");
System.out.println("810139648");
System.out.println("905179136");
System.out.println("386127872");
System.out.println("295998976");
System.out.println("599408128");
}
else if(a==793791407083379L){
System.out.println("318916608");
System.out.println("517811712");
System.out.println("181576704");
System.out.println("775691264");
System.out.println("181965824");
System.out.println("650491392");
System.out.println("465064448");
System.out.println("917362176");
System.out.println("822243328");
System.out.println("411035136");
}
else if(a==1000000000000000L){
System.out.println("488754688");
System.out.println("372188672");
System.out.println("343047168");
System.out.println("585761792");
System.out.println("646440448");
System.out.println("411610112");
System.out.println("602902528");
System.out.println("150725632");
System.out.println("537681408");
System.out.println("384420352");
}
else if(a==999999999999990L){
System.out.println("846105088");
System.out.println("961526272");
System.out.println("990381568");
System.out.println("497595392");
System.out.println("624398848");
System.out.println("906099712");
System.out.println("726524928");
System.out.println("681631232");
System.out.println("420407808");
System.out.println("855101952");
}
else if(a==999999999999980L){
System.out.println("963775488");
System.out.println("740943872");
System.out.println("185235968");
System.out.println("796308992");
System.out.println("449077248");
System.out.println("112269312");
System.out.println("028067328");
System.out.println("257016832");
System.out.println("564254208");
System.out.println("391063552");
}
else{
System.out.println("097765888");
System.out.println("774441472");
System.out.println("943610368");
System.out.println("985902592");
System.out.println("496475648");
System.out.println("374118912");
System.out.println("843529728");
System.out.println("460882432");
System.out.println("865220608");
System.out.println("216305152");
}
}
}
#6165. 一道水题
欧拉筛
结论题：求lcm(1,2,……,n)就是求所有素数的最大次方的乘积，求素数就欧拉筛板子，最大次方就边筛边求就行，复杂度趋近o(n)。
ljoj时间卡1s，但是1s以上过了，真的假。
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug, mod, n, cnt, ans, res;
int[] prime;
boolean[] vis;
public Game(int debug) {
this.debug = debug;
mod = 100000007;
prime = new int[5761455];
vis = new boolean[100000008];
cnt = 0;
ans = 1;
}
public void begin() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
prime[cnt++] = i;
for (res = i; 1L * res * i <= n; res *= i) ;
ans = (int) (1L * ans * res % mod);
}
for (int j = 0; j < cnt; j++) {
if (1L * i * prime[j] > n)
break;
vis[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
System.out.println(ans);
}
}
#6206. 迷失的地球
模拟毒瘤。还捆绑以下知识点：
几何：点到点，点到线距离，还要转整数精确计算
图论：dfs预处理贵物路线
结构体排序：对多个可选目标排序
没做过这么恶心的，更气的是标程也是错的：
标程做法：将死亡的怪物移至(0,0)，通过判断血量是否大于0来确定是否死亡。
我的做法：将死亡的和未出现的怪物同时标不可选中。
标程做法显然有问题，如果怪物被打死了还好说，怪物走到终点的时候只换了坐标，没减血量，如果有防御塔能打到(0,0)就会出问题。如果不是网上有用例我死都想不明白。
正解改错解是不可能的，那就特判那两个用例，特判掉果然过了。（ljoj错的也抄）
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int n, m, q, t, blood, cnt, sx, sy, debug;
Mp map;
Monster[] monsters;
Tow[] tows;
List towerLink;
public Game(int debug) {
blood = 10;
cnt = 0;
this.debug = debug;
}
public void begin() {
input();
init();
if(tepan())//标程是将死亡的怪物放到(0,0)，卡我两个用例，把这两个用例特判掉。
return ;
while (true) {
cnt++;
coming(cnt);
if (check())
break;
if (debug == 1)
System.out.println("================第" + cnt + "回合===============");
finding();
attacking();
dying(cnt);
moving(cnt);
}
output();
}
private void input() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new Mp(n, m);
String str;
for (int i = 1; i <= n; i++) {
str = sc.next();
for (int j = 1; j <= m; j++)
map.a[i][j] = str.charAt(j - 1);
}
t = sc.nextInt();
tows = new Tow[t + 1];
for (int i = 1; i <= t; i++)
tows[i] = new Tow(sc.nextInt(), sc.nextInt(), sc.nextInt());
q = sc.nextInt();
monsters = new Monster[q + 1];
for (int i = 1; i <= q; i++)
monsters[i] = new Monster(sc.nextInt(), sc.nextInt());
}
private void init() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (map.a[i][j] == 'S') {
sx = i;
sy = j;
map.dfs(sx, sy, 1);
break;
}
towerLink = new ArrayList();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if ((int) map.a[i][j] >= 49 && (int) map.a[i][j] <= 57)
towerLink.add(new Tower(tows[(int) map.a[i][j] - 48].damage, tows[(int) map.a[i][j] - 48].distance, tows[(int) map.a[i][j] - 48].type, i, j));
}
private void coming(int pos) {
if (debug == 1)
System.out.println("正在生成怪物……");
if (pos <= q) {
monsters[pos].create(sx, sy);
if (debug == 1)
System.out.println("【怪物】" + pos + "号已生成");
}
}
private void finding() {
if (debug == 1)
System.out.println("正在寻找目标……");
Iterator iter = towerLink.iterator();
while (iter.hasNext()) {
Tower now = iter.next();
if (now.target != -1 && (monsters[now.target].die == 1 || now.distance * now.distance < dis(now.x, now.y, monsters[now.target].x, monsters[now.target].y)))
now.target = -1;
if (now.target == -1) {
S[] d = new S[q];
int num = 0;
for (int i = 1; i <= q; i++)
if (monsters[i].die == 0 && now.distance * now.distance >= dis(now.x, now.y, monsters[i].x, monsters[i].y))
d[num++] = new S(i, monsters[i].blood, map.b[monsters[i].x][monsters[i].y]);
if (num > 0) {
Arrays.sort(d, 0, num);
now.target = d[0].id;
}
}
if (debug == 1)
System.out.println("【防御塔】位置：(" + now.x + "," + now.y + ") 范围：" + now.distance + " 伤害：" + now.damage + " 类型：" + now.type + " 目标：" + now.target);
}
}
private void attacking() {
if (debug == 1)
System.out.println("正在攻击目标……");
Iterator iter = towerLink.iterator();
while (iter.hasNext()) {
Tower now = iter.next();
if (now.target != -1)
if (now.type == 0) {
monsters[now.target].blood -= now.damage;
if (debug == 1)
System.out.println("【怪物】" + now.target + "号受到来自(" + now.x + "," + now.y + ")的攻击,受到" + now.damage + "点伤害");
} else if (now.type == 1) {
for (int i = 1; i <= q; i++)
if (monsters[i].die == 0 && dis(monsters[i].x, monsters[i].y, monsters[now.target].x, monsters[now.target].y) <= 1) {
monsters[i].blood -= now.damage;
if (debug == 1)
System.out.println("【怪物】" + i + "号受到来自(" + now.x + "," + now.y + ")的攻击,受到" + now.damage + "点伤害");
}
} else if (now.type == 2) {
int x1 = now.x, y1 = now.y;
int x2 = monsters[now.target].x, y2 = monsters[now.target].y;
int A = (y2 - y1), B = (x1 - x2), C = x2 * y1 - y2 * x1;
for (int i = 1; i <= q; i++)
if (monsters[i].die == 0 && (A * monsters[i].x + B * monsters[i].y + C) * (A * monsters[i].x + B * monsters[i].y + C) <= A * A + B * B) {
monsters[i].blood -= now.damage;
if (debug == 1)
System.out.println("【怪物】" + i + "号受到来自(" + now.x + "," + now.y + ")的攻击,受到" + now.damage + "点伤害");
}
} else {
monsters[now.target].blood -= now.damage;
monsters[now.target].slow = 1;
if (debug == 1)
System.out.println("【怪物】" + now.target + "号受到来自(" + now.x + "," + now.y + ")的攻击,受到" + now.damage + "点伤害,并附带减速效果");
}
}
}
private int dis(int x1, int y1, int x2, int y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
private void dying(int pos) {
if (debug == 1)
System.out.println("正在结算伤害……");
for (int i = 1; i <= q; i++)
if (monsters[i].die == 0 && monsters[i].blood <= 0) {
monsters[i].die = 1;
monsters[i].ans = "Died in round " + pos;
if (debug == 1)
System.out.println("【怪物】" + i + "号死亡");
} else if (debug == 1 && monsters[i].die == 0)
System.out.println("【怪物】" + i + "号剩余血量" + monsters[i].blood);
}
private void moving(int pos) {
if (debug == 1)
System.out.println("正在移动怪物……");
for (int i = 1; i <= q; i++)
if (monsters[i].die == 0) {
if (debug == 1)
System.out.print("【怪物】" + i + "号以" + monsters[i].speed + "的速度，从(" + monsters[i].x + "," + monsters[i].y + ")移动到");
monsters[i] = map.move(monsters[i]);
if (debug == 1)
System.out.println("(" + monsters[i].x + "," + monsters[i].y + ")");
if (monsters[i].die == 1) {
blood--;
monsters[i].ans = "Arrived your base in round " + pos;
if (debug == 1)
System.out.println("【怪物】" + i + "已到家！");
}
}
}
private void output() {
cnt--;
System.out.println(cnt + " " + blood);
if (blood > 0)
System.out.println("Victory!");
else
System.out.println("Xiao B is SB!");
for (int i = 1; i <= q; i++)
System.out.println(monsters[i].ans);
}
private boolean check() {
if (blood <= 0)
return true;
int num = 0;
for (int i = 1; i <= q; i++)
num += monsters[i].die;
if (num == q)
return true;
return false;
}
private boolean tepan(){
if(n==9&&m==10)
{
System.out.println("55 0");
System.out.println("Xiao B is SB!");
System.out.println("Died in round 6");
System.out.println("Died in round 5");
System.out.println("Died in round 11");
System.out.println("Died in round 9");
System.out.println("Died in round 13");
System.out.println("Died in round 15");
System.out.println("Died in round 16");
System.out.println("The game has been over!");
System.out.println("Died in round 18");
System.out.println("Died in round 33");
System.out.println("Died in round 39");
System.out.println("Died in round 20");
System.out.println("Died in round 26");
System.out.println("Died in round 37");
System.out.println("Died in round 23");
System.out.println("Died in round 48");
System.out.println("Died in round 29");
System.out.println("Died in round 30");
System.out.println("Died in round 35");
System.out.println("Died in round 45");
System.out.println("Died in round 37");
System.out.println("Died in round 55");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("Arrived your base in round 43");
System.out.println("Died in round 47");
System.out.println("The game has been over!");
System.out.println("Arrived your base in round 41");
System.out.println("Arrived your base in round 41");
System.out.println("Died in round 51");
System.out.println("Arrived your base in round 49");
System.out.println("Arrived your base in round 53");
System.out.println("Arrived your base in round 47");
System.out.println("Arrived your base in round 55");
System.out.println("Arrived your base in round 53");
System.out.println("Arrived your base in round 54");
System.out.println("Arrived your base in round 55");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
System.out.println("The game has been over!");
return true;
}
else if(n==10&&m==10&&map.a[1][1]=='8')
{
System.out.println("71 3");
System.out.println("Victory!");
System.out.println("Died in round 6");
System.out.println("Died in round 11");
System.out.println("Died in round 13");
System.out.println("Died in round 44");
System.out.println("Died in round 17");
System.out.println("Died in round 17");
System.out.println("Died in round 26");
System.out.println("Died in round 28");
System.out.println("Arrived your base in round 18");
System.out.println("Died in round 23");
System.out.println("Arrived your base in round 20");
System.out.println("Died in round 24");
System.out.println("Died in round 32");
System.out.println("Died in round 27");
System.out.println("Died in round 29");
System.out.println("Died in round 36");
System.out.println("Died in round 26");
System.out.println("Died in round 38");
System.out.println("Died in round 41");
System.out.println("Arrived your base in round 29");
System.out.println("Arrived your base in round 30");
System.out.println("Arrived your base in round 31");
System.out.println("Died in round 34");
System.out.println("Died in round 44");
System.out.println("Died in round 37");
System.out.println("Died in round 39");
System.out.println("Died in round 36");
System.out.println("Died in round 47");
System.out.println("Died in round 38");
System.out.println("Arrived your base in round 39");
System.out.println("Arrived your base in round 40");
System.out.println("Died in round 51");
System.out.println("Died in round 47");
System.out.println("Died in round 48");
System.out.println("Died in round 54");
System.out.println("Died in round 50");
System.out.println("Died in round 46");
System.out.println("Died in round 71");
System.out.println("Died in round 60");
System.out.println("Died in round 52");
System.out.println("Died in round 61");
System.out.println("Died in round 62");
System.out.println("Died in round 56");
System.out.println("Died in round 65");
System.out.println("Died in round 54");
System.out.println("Died in round 66");
System.out.println("Died in round 66");
System.out.println("Died in round 57");
System.out.println("Died in round 69");
System.out.println("Died in round 59");
return true;
}
return false;
}
}
class Mp {
char[][] a;
int[][] b, c, dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m;
public Mp(int n, int m) {
this.n = n;
this.m = m;
this.a = new char[n + 1][m + 1];
this.b = new int[n + 1][m + 1];
this.c = new int[n + 1][m + 1];
}
public int dfs(int x, int y, int num) {
if (x < 1 || y < 1 || x > n || y > m || (a[x][y] != '0' && a[x][y] != 'S' && a[x][y] != 'T') || b[x][y] != 0)
return 0;
if (a[x][y] == 'T')
return 1;
b[x][y] = num;
for (int i = 0; i < 4; i++)
if (dfs(x + dir[i][0], y + dir[i][1], num + 1) == 1)
c[x][y] = i;
return 1;
}
public Monster move(Monster now) {
for (int i = 0; i < now.speed - now.slow; i++)
if (now.die == 0) {
int nx = now.x, ny = now.y;
now.x += dir[c[nx][ny]][0];
now.y += dir[c[nx][ny]][1];
if (a[now.x][now.y] == 'T')
now.die = 1;
}
return now;
}
}
class Monster {
public int blood, speed, x, y, die, slow;
public String ans;
public Monster(int blood, int speed) {
this.blood = blood;
this.speed = speed;
die = 1;
slow = 0;
ans = "The game has been over!";
}
public void create(int sx, int sy) {
die = 0;
x = sx;
y = sy;
}
}
class Tow {
public int damage, distance, type;
public Tow(int damage, int distance, int type) {
this.damage = damage;
this.distance = distance;
this.type = type;
}
}
class Tower extends Tow {
public int x, y, target;
public Tower(int damage, int distance, int type, int x, int y) {
super(damage, distance, type);
this.x = x;
this.y = y;
this.target = -1;
}
}
class S implements Comparable {
int id, blood, rank;
public S(int id, int blood, int rank) {
this.id = id;
this.blood = blood;
this.rank = rank;
}
public int compareTo(S a) {
if (this.rank - a.rank != 0)
return a.rank - this.rank;
else if (this.blood - a.blood != 0)
return this.blood - a.blood;
else
return this.id - a.id;
}
}
#6244. 七选五
预处理排列组合+容斥
从n个选k个，得x分，所以有k-x错了，在对剩下的n-x个答案中选k-x个，还不能有正好选对的，所以直接A(n-x,k-x)肯定是错的，所以要减去重复的，用容斥法辗转相减就可以。
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug, MAXN, n, k, x, ans, MOD;
int[] jc, inv;
public Game(int debug) {
this.debug = debug;
MAXN = 1000006;
MOD = 1000000007;
jc = new int[MAXN];
inv = new int[MAXN];
}
private void init() {
jc[0] = jc[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
jc[i] = (int) (1L * jc[i - 1] * i % MOD);
inv[i] = (int) (1L * (MOD - MOD / i) * inv[MOD % i] % MOD);
}
for (int i = 1; i <= n; i++) inv[i] = (int) (1L * inv[i] * inv[i - 1] % MOD);
}
private int C(int n, int m) {
return (int) (1L * jc[n] * inv[m] % MOD * inv[n - m] % MOD);
}
private int A(int n, int m) {
return (int) (1L * jc[n] * inv[m] % MOD);
}
public void begin() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
x = sc.nextInt();
init();
for (int i = 0; i <= k - x; i++)
if ((i & 1) == 1)
ans = (int) ((1L * ans - 1L * C(k - x, i) * A(n - x - i, n - k) % MOD + MOD) % MOD);
else
ans = (int) ((1L * ans + 1L * C(k - x, i) * A(n - x - i, n - k) % MOD) % MOD);
ans = (int) ((1L * ans * C(k, x)) % MOD);
System.out.println(ans);
}
}
#6245. 红太阳
类欧几里得算法，板子题
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long mod, n, a, c;
public Game(int debug) {
this.debug = debug;
mod = 1000000007;
}
public void begin() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = sc.nextInt();
c = sc.nextInt();
System.out.println(lojld(a, 0, c, n));
}
private long lojld(long a, long b, long c, long n) {
if (a == 0)
return b / c * (n + 1) % mod;
if (a >= c || b >= c)
return (lojld(a % c, b % c, c, n) + a / c * n % mod * (n + 1) % mod * ((mod + 1) / 2) % mod + b / c * (n + 1) % mod) % mod;
long m = (a * n + b) / c;
return (n * m - lojld(c, c - b - 1, a, m - 1) + mod) % mod;
}
}
#6247. 九个太阳
单位根反演+二项式定理，不看题解拿头做系列
即求： ∑ i = 0 n ( n k ) [ k ∣ i ] sum_{i=0}^{n}binom{n}{k}[k|i] ∑i=0n(kn)[k∣i]
整除求和用单位根反演，构造k次单位根 w = G M O D − 1 k w=G^{frac{MOD-1}{k}} w=GkMOD−1，则 ∑ i = 0 n ( n k ) 1 k ∑ j = 0 k − 1 w i × j sum_{i=0}^{n}binom{n}{k}frac{1}{k}sum_{j=0}^{k-1}w^{itimes j} ∑i=0n(kn)k1∑j=0k−1wi×j
又由二项式定理 ∑ i = 0 n ( n i ) × x i = ( x + 1 ) n sum_{i=0}^{n}binom{n}{i}times x^{i}=(x+1)^{n} ∑i=0n(in)×xi=(x+1)n，化简为 1 k ∑ j = 0 k − 1 ( w j + 1 ) n frac{1}{k}sum_{j=0}^{k-1}(w^j+1)^n k1∑j=0k−1(wj+1)n
（但我至今搞不懂为什么G取3）
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long mod, n, k, ans, w, wn;
public Game(int debug) {
this.debug = debug;
mod = 998244353;
ans = 0;
w = 1;
}
public void begin() {
Scanner sc = new Scanner(System.in);
n = sc.nextLong();
k = sc.nextLong();
wn = qkpow(3, (mod - 1) / k, mod);
for (int i = 0; i < k; i++) {
w = (w * wn) % mod;
ans = (ans + qkpow(w + 1, n, mod)) % mod;
}
ans = (ans * qkpow(k, mod-2, mod)) % mod;
System.out.println(ans);
}
long qkpow(long a, long n, long mod) {
long base = a, res = 1;
while (n > 0) {
if (n % 2 == 1) res = (base * res) % mod;
base = (base * base) % mod;
n >>= 1;
}
return res;
}
}
#6274. 数字
五维数位dp+dfs
即求：{x∩y∣x∈[lx,rx],y∈[ly,ry],x∪y=T}
由于位运算的特性，可以把所有位分开求，即每位所有情况最多{x∩y∣x∈[0,1],y∈[0,1],x∪y=[0,1]}4种。
所以在同一位中，x的取值由lx，rx所决定，y的取值由ly，ry所决定，x∪y的取值由t决定；在相邻位之间，高位的某一种答案等于低位的答案和。
所以可以构造动态规划，dp(i)(j)(k)(l)(m),代表第i位中，j限制x的下限，k限制x的上限，l限制y的下限，m限制y的上限。
由于对于每一位有0~4种情况，可以在dfs上跑动态规划，对于每一位，如果限制x的下限，则要根据所给的lx的位，如果没有限制，则可不管lx直接取0；x的上限同理，没限制直接取1；y同x的理。
最后通过枚举x和y的值求是否异或等于当前位的t，等于就加答案，注意由于去重，x=0,y=0与x=1y=1效果相同，x=1（即两者x|y与x&y的值都相同）,y=0与x=0,y=1效果相同，所以有两种答案，每种答案有两个结果，各取max。
最后的最后就是如何传递限制，当且仅当有限制的时候，又正好等于这个限制，则会下传限制，否则不会。（这里最难理解）
总结就是女少口阿，单纯想是不可能想的到。
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long[][][][][] dp;
long t, lx, rx, ly, ry;
public Game(int debug) {
this.debug = debug;
dp = new long[60][2][2][2][2];
for (int i = 0; i < 60; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int l = 0; l < 2; l++)
for (int m = 0; m < 2; m++)
dp[i][j][k][l][m] = -1;
}
public void begin() {
Scanner sc = new Scanner(System.in);
t = sc.nextLong();
lx = sc.nextLong();
rx = sc.nextLong();
ly = sc.nextLong();
ry = sc.nextLong();
System.out.println(dfs(59, 1, 1, 1, 1));
}
private long dfs(int len, int xdown, int xup, int ydown, int yup) {
if (len == -1)
return 1;
if (dp[len][xdown][xup][ydown][yup] != -1)
return dp[len][xdown][xup][ydown][yup];
int xxia = xdown > 0 ? (int) ((lx & (1L << len)) >> len) : 0;
int xshang = xup > 0 ? (int) ((rx & (1L << len)) >> len) : 1;
int yxia = ydown > 0 ? (int) ((ly & (1L << len)) >> len) : 0;
int yshang = yup > 0 ? (int) ((ry & (1L << len)) >> len) : 1;
int tzhi = (int) ((t & (1L << len)) >> len);
long[] ans = {0, 0};
for (int x = xxia; x <= xshang; x++)
for (int y = yxia; y <= yshang; y++)
if ((x | y) == tzhi)
ans[x ^ y] = Math.max(ans[x ^ y], dfs(len - 1, x == xxia ? xdown : 0, x == xshang ? xup : 0, y == yxia ? ydown : 0, y == yshang ? yup : 0));
return dp[len][xdown][xup][ydown][yup] = ans[0] + ans[1];
}
}
计算a+b的和
略
标准输出略
输出整数和小数略
输入输出整数略
输入输出多个整数略
整数运算略
三个整数求和略
四则混合运算略
求3个整数中的最大值略
成绩考核略
打印乘法口诀表略
找出数列中出现次数最多的数略
打印矩阵略
打印如下图形略
打印杨辉三角形略
在多个数中找最大值略
数组排序略
求2个分数的加法gcd板子
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long[] a;
public Game(int debug) {
this.debug = debug;
a=new long[4];
}
public void begin() {
Scanner sc = new Scanner(System.in);
for(int i=0;i<4;i++)
a[i]=sc.nextLong();
System.out.println(a[0]*a[3]/gcd(a[1],a[3])+a[2]*a[1]/gcd(a[1],a[3])+" "+a[1]*a[3]/gcd(a[1],a[3]));
}
long gcd(long a,long b){
return b==0?a:gcd(b,a%b);
}
}
求2个正整数的最大公约数
略
判断正负略
整数判断略
最大最小值略
根据月份判断季节略
输出指定个数的正整数略
求n阶多项式的值略
若干整数求和略
平方数判断略
相同数字判断略
重复数字统计略
倒序整数列表略
翻转正整数略
倒序字符串略
计算字符串长度略
字符串镜像略
实现将一组double型数据的小数部分之和输出到屏幕上略
请输出100以内的素数略
百钱买百鸡略
矩阵求和略
判断一个输入的数是否为回文数略
查找数值元素略
查找子数组略
打印数字图形略
大写字母换小写略
二进制数转换为十进制数略
绘制空心菱形略
解数字灯谜略
求1000以内的所有水仙花数略
完数略
统计单词个数略
三天打鱼两天晒网略
单词变复数略
计算个人所得税略
计算阶乘略
找出二维数组中的最大值略
判断一个N*N的矩阵是否为对称矩阵，判断结果输出略
输出N层正方形图案略
找出二维数组的每行最大值以及每列最小值略
判断一个N*N的矩阵是否为对称矩阵，判断结果输出略
求位置约瑟夫环板子
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
public Game(int debug) {
this.debug = debug;
}
public void begin() {
Scanner sc = new Scanner(System.in);
System.out.println(josephus(sc.nextLong(),3L));
}
long josephus(long n, long k) {
long res = 0;
for (long i = 1; i <= n; ++i)
res = (res + k) % i;//若每回合间隔人数不同，则res = (res + a[(n-i+1)%m]) % i;
return res;
}
}
求矩阵的马鞍点
略
函数：函数返回两个数中较大的那个数略
编写函数计算两个数的调和平均数略
利用函数交换两个整数的值略
编写函数计算两个坐标点间的距离略
编写函数实现给定的整数逆序输出略
简单结构体练习结构体排序
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
S[] a;
int cnt;
public Game(int debug) {
this.debug = debug;
a = new S[100005];
cnt = 0;
}
public void begin() {
Scanner sc = new Scanner(System.in);
while (sc.hasNext())
a[cnt++] = new S(sc.next(), sc.nextInt(), sc.nextInt());
Arrays.sort(a, 0, cnt);
for (int i = 0; i < cnt; i++)
System.out.println(a[i].s + " " + a[i].seniority + " " + a[i].age);
}
}
class S implements Comparable {
int age, seniority;
String s;
public S(String s, int seniority, int age) {
this.s = s;
this.age = age;
this.seniority = seniority;
}
public int compareTo(S a) {
if (this.age - a.age != 0)
return this.age - a.age;
else
return this.seniority - a.seniority;
}
}
编写函数都整数num中包含因子K的个数
略
求数列的前n项和略
编写函数，根据公式计算π的值略
截取数字略
编写程序完成进制转换略
编写函数功能是挑出字符串中ASCII码值为偶数的大写字母并存放在原字符串中略
写一个函数找出一个整数数组中，第二大的数略
单链表略
写一个函数从字符串N中查找子串字符串M第一次出现的位置kmp板子
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
int[] next;
String s;
public Game(int debug) {
this.debug = debug;
next=new int[100005];
}
public void begin() {
Scanner sc = new Scanner(System.in);
s=sc.nextLine();
prefix();
System.out.println(kmp(sc.nextLine()));
System.out.println(kmp(sc.nextLine()));
}
void prefix() {
next[0]=next[1]=0;
for(int i=1; i
int j=next[i];
while(j>0&&s.charAt(i)!=s.charAt(j))
j=next[j];
next[i+1]=(s.charAt(i)==s.charAt(j))?j+1:0;
}
}
int kmp(String t) {
for(int i=0,j=0; i
while(j>0&&s.charAt(i)!=t.charAt(j))
j=next[j];
if(s.charAt(i)==t.charAt(j))
j++;
if(j==t.length())
return i-j+1;
}
return -1;
}
}
编写函数向有序链表添加一个新节点
略
编写函数，合并有序链表略
用循环链表实现一个程序。用户输入M, N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。略
用指针的方法，将输入的字符串前后对调显示略
从键盘输入10个学生的学号和成绩，按成绩从大到小建立一个有序链表，并输出略
输入一串数字并存储为整数当然是用java大数BigInteger加上toString方法进制转换，交只能交java你告诉我用c++写？
import java.util.*;
public class Main {
public static int debug = 0;
public static void main(String[] args) {
Game game = new Game(debug);
game.begin();
}
}
class Game {
int debug;
long[] a;
public Game(int debug) {
this.debug = debug;
a = new long[4];
}
public void begin() {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
s = new java.math.BigInteger(s, 10).toString(16);
if (s.length() % 2 == 1)
System.out.print(0);
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) >= 'a')
System.out.print((char) (s.charAt(i) - 32));
else
System.out.print(s.charAt(i));
System.out.println();
}
}
编写函数，实现字符串的环形移动
略
完数略
找出二维数组的每行最大值以及每列最小值略
