text:
# OpenGL Clarification for a directX ASCII file...

This topic is 3378 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok here is an example of a directX file I generated using a 3D modeling software, since i am not using directX, but writing a loader for this file, I would like to clarify what does each individual part of it mean.

Frame RootFrame {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.000000,1.000000,0.000000,
0.000000,1.000000,0.000000,0.000000,
0.000000,0.000000,0.000000,1.000000
}
Frame Bone_000 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.000000,1.000000,0.000000,
0.000000,-1.000000,0.000000,0.000000,
0.000000,0.000000,0.000000,1.000000
}
Frame Bone_001 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,1.000000,-0.002400,0.000000,
0.000000,0.002400,1.000000,0.000000,
0.000000,1.000000,0.000000,1.000000
}
Frame Bone_002 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.999400,0.034500,0.000000,
0.000000,-0.034500,0.999400,0.000000,
0.000000,1.256400,0.000000,1.000000
}
Frame Bone_003 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.998000,-0.062600,0.000000,
0.000000,0.062600,0.998000,0.000000,
0.000000,1.257200,0.000000,1.000000
}
Frame Bone_004 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.997900,0.064500,0.000000,
0.000000,-0.064500,0.997900,0.000000,
0.000000,1.538700,0.000000,1.000000
}
Frame Bone_005 {

FrameTransformMatrix {
1.000000,0.000000,0.000000,0.000000,
0.000000,0.995700,-0.092500,0.000000,
0.000000,0.092500,0.995700,0.000000,
0.000000,1.192200,0.000000,1.000000
}
}
}
}
}
}
}  // End of the Bone Bone

Am I right to say that these are the representations of the armatures in my model's underlying skeleton? They are each local matrices, right?(Lets call them localMatrix for now) What does rootFrame do? From my guess it isn't a bone, it is just a matrix which we have to multiply against to find the "world matrix", (i'm assuming that these are individual local bone matrices laid out in a hierarchy, correct?) So, next, in what way do I combine these matrices, is it top to bottom or bottom to top? Bone_005(worldmatrix) = 005 * 004 * 003 * 002 * 001 * 000 * rootFrame or is it the other way round? Bone_005(worldmatrix) =rootFrame * 000 * 001 * 002 * 003 * 004 * 005 or is rootFrame multiplied in the last? I'm quite confused about this, good if someone could clarify with me. So lets say I store these matrices in an array with an ascending order(according to bone name, 000 to 005), with rootFrame individually stored... so lets continue...
Mesh {
132;
0.442900; 0.268300; 8.127200;,
0.442900; -0.368400; 8.128700;,
-0.428400; 0.268300; 8.127200;,
0.442900; -0.368400; 8.128700;,
-0.428400; -0.368400; 8.128700;,
-0.428400; 0.268300; 8.127200;,
0.442900; -0.372100; 6.574900;,
-0.428400; -0.372100; 6.574900;,
-0.428400; -0.368400; 8.128700;,
0.442900; -0.372100; 6.574900;,
-0.428400; -0.368400; 8.128700;,
0.442900; -0.368400; 8.128700;,
-0.428400; -0.372100; 6.574900;,
-0.428400; 0.264600; 6.573400;,
-0.428400; 0.268300; 8.127200;,
-0.428400; -0.372100; 6.574900;,
-0.428400; 0.268300; 8.127200;,
-0.428400; -0.368400; 8.128700;,
0.442900; 0.264600; 6.573400;,
0.442900; -0.372100; 6.574900;,
0.442900; -0.368400; 8.128700;,
0.442900; 0.264600; 6.573400;,
0.442900; -0.368400; 8.128700;,
0.442900; 0.268300; 8.127200;,
-0.428400; 0.264600; 6.573400;,
0.442900; 0.264600; 6.573400;,
-0.428400; 0.268300; 8.127200;,
0.442900; 0.264600; 6.573400;,
0.442900; 0.268300; 8.127200;,
-0.428400; 0.268300; 8.127200;,
-0.428400; 0.262000; 5.477000;,
0.442900; 0.262000; 5.477000;,
-0.428400; 0.264600; 6.573400;,
0.442900; 0.262000; 5.477000;,
0.442900; 0.264600; 6.573400;,
-0.428400; 0.264600; 6.573400;,
0.442900; 0.262000; 5.477000;,
0.442900; -0.374700; 5.478500;,
0.442900; 0.264600; 6.573400;,
0.442900; -0.374700; 5.478500;,
0.442900; -0.372100; 6.574900;,
0.442900; 0.264600; 6.573400;,
-0.428400; -0.374700; 5.478500;,
-0.428400; 0.262000; 5.477000;,
-0.428400; -0.372100; 6.574900;,
-0.428400; 0.262000; 5.477000;,
-0.428400; 0.264600; 6.573400;,
-0.428400; -0.372100; 6.574900;,
0.442900; -0.374700; 5.478500;,
-0.428400; -0.374700; 5.478500;,
-0.428400; -0.372100; 6.574900;,
0.442900; -0.374700; 5.478500;,
-0.428400; -0.372100; 6.574900;,
0.442900; -0.372100; 6.574900;,
0.442900; -0.378500; 3.887200;,
-0.428400; -0.378500; 3.887200;,
-0.428400; -0.374700; 5.478500;,
0.442900; -0.378500; 3.887200;,
-0.428400; -0.374700; 5.478500;,
0.442900; -0.374700; 5.478500;,
-0.428400; -0.378500; 3.887200;,
-0.428400; 0.258100; 3.885700;,
-0.428400; -0.374700; 5.478500;,
-0.428400; 0.258100; 3.885700;,
-0.428400; 0.262000; 5.477000;,
-0.428400; -0.374700; 5.478500;,
0.442900; 0.258100; 3.885700;,
0.442900; -0.378500; 3.887200;,
0.442900; 0.262000; 5.477000;,
0.442900; -0.378500; 3.887200;,
0.442900; -0.374700; 5.478500;,
0.442900; 0.262000; 5.477000;,
-0.428400; 0.258100; 3.885700;,
0.442900; 0.258100; 3.885700;,
-0.428400; 0.262000; 5.477000;,
0.442900; 0.258100; 3.885700;,
0.442900; 0.262000; 5.477000;,
-0.428400; 0.262000; 5.477000;,
-0.428400; 0.254400; 2.325300;,
0.442900; 0.254400; 2.325300;,
-0.428400; 0.258100; 3.885700;,
0.442900; 0.254400; 2.325300;,
0.442900; 0.258100; 3.885700;,
-0.428400; 0.258100; 3.885700;,
0.442900; 0.254400; 2.325300;,
0.442900; -0.382300; 2.326900;,
0.442900; 0.258100; 3.885700;,
0.442900; -0.382300; 2.326900;,
0.442900; -0.378500; 3.887200;,
0.442900; 0.258100; 3.885700;,
-0.428400; -0.382300; 2.326900;,
-0.428400; 0.254400; 2.325300;,
-0.428400; -0.378500; 3.887200;,
-0.428400; 0.254400; 2.325300;,
-0.428400; 0.258100; 3.885700;,
-0.428400; -0.378500; 3.887200;,
0.442900; -0.382300; 2.326900;,
-0.428400; -0.382300; 2.326900;,
-0.428400; -0.378500; 3.887200;,
0.442900; -0.382300; 2.326900;,
-0.428400; -0.378500; 3.887200;,
0.442900; -0.378500; 3.887200;,
0.442900; -0.388200; -0.136900;,
0.442900; 0.248500; -0.138400;,
-0.428400; -0.388200; -0.136900;,
0.442900; 0.248500; -0.138400;,
-0.428400; 0.248500; -0.138400;,
-0.428400; -0.388200; -0.136900;,
-0.428400; 0.254400; 2.325300;,
-0.428400; -0.382300; 2.326900;,
-0.428400; -0.388200; -0.136900;,
-0.428400; 0.254400; 2.325300;,
-0.428400; -0.388200; -0.136900;,
-0.428400; 0.248500; -0.138400;,
0.442900; 0.248500; -0.138400;,
0.442900; -0.388200; -0.136900;,
0.442900; 0.254400; 2.325300;,
0.442900; -0.388200; -0.136900;,
0.442900; -0.382300; 2.326900;,
0.442900; 0.254400; 2.325300;,
0.442900; -0.388200; -0.136900;,
-0.428400; -0.388200; -0.136900;,
-0.428400; -0.382300; 2.326900;,
0.442900; -0.388200; -0.136900;,
-0.428400; -0.382300; 2.326900;,
0.442900; -0.382300; 2.326900;,
0.442900; 0.248500; -0.138400;,
0.442900; 0.254400; 2.325300;,
-0.428400; 0.254400; 2.325300;,
0.442900; 0.248500; -0.138400;,
-0.428400; 0.254400; 2.325300;,
-0.428400; 0.248500; -0.138400;;
44;
3; 0, 2, 1;,
3; 3, 5, 4;,
3; 6, 8, 7;,
3; 9, 11, 10;,
3; 12, 14, 13;,
3; 15, 17, 16;,
3; 18, 20, 19;,
3; 21, 23, 22;,
3; 24, 26, 25;,
3; 27, 29, 28;,
3; 30, 32, 31;,
3; 33, 35, 34;,
3; 36, 38, 37;,
3; 39, 41, 40;,
3; 42, 44, 43;,
3; 45, 47, 46;,
3; 48, 50, 49;,
3; 51, 53, 52;,
3; 54, 56, 55;,
3; 57, 59, 58;,
3; 60, 62, 61;,
3; 63, 65, 64;,
3; 66, 68, 67;,
3; 69, 71, 70;,
3; 72, 74, 73;,
3; 75, 77, 76;,
3; 78, 80, 79;,
3; 81, 83, 82;,
3; 84, 86, 85;,
3; 87, 89, 88;,
3; 90, 92, 91;,
3; 93, 95, 94;,
3; 96, 98, 97;,
3; 99, 101, 100;,
3; 102, 104, 103;,
3; 105, 107, 106;,
3; 108, 110, 109;,
3; 111, 113, 112;,
3; 114, 116, 115;,
3; 117, 119, 118;,
3; 120, 122, 121;,
3; 123, 125, 124;,
3; 126, 128, 127;,
3; 129, 131, 130;;
MeshMaterialList {
2;
44;
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1;;
Material Material {
0.800000; 0.800000; 0.800000;1.0;;
0.500000;
1.000000; 1.000000; 1.000000;;
0.0; 0.0; 0.0;;
}  //End of Material
Material Mat1 {
1.0; 1.0; 1.0; 1.0;;
1.0;
1.0; 1.0; 1.0;;
0.0; 0.0; 0.0;;
TextureFilename {    "wood-planks-texture.j";  }
}  // End of Material
}  //End of MeshMaterialList
MeshNormals {
132;
-0.577349; -0.577349; 0.577349;,
-0.666646; -0.666646; -0.333323;,
0.577349; -0.577349; 0.577349;,
-0.666646; -0.666646; -0.333323;,
0.408246; -0.408246; -0.816492;,
0.577349; -0.577349; 0.577349;,
-0.554674; 0.000000; -0.832026;,
0.799982; 0.000000; -0.599994;,
0.408246; -0.408246; -0.816492;,
-0.554674; 0.000000; -0.832026;,
0.408246; -0.408246; -0.816492;,
-0.666646; -0.666646; -0.333323;,
0.799982; 0.000000; -0.599994;,
0.554674; 0.000000; 0.832026;,
0.577349; -0.577349; 0.577349;,
0.799982; 0.000000; -0.599994;,
0.577349; -0.577349; 0.577349;,
0.408246; -0.408246; -0.816492;,
-0.799982; 0.000000; 0.599994;,
-0.554674; 0.000000; -0.832026;,
-0.666646; -0.666646; -0.333323;,
-0.799982; 0.000000; 0.599994;,
-0.666646; -0.666646; -0.333323;,
-0.577349; -0.577349; 0.577349;,
0.554674; 0.000000; 0.832026;,
-0.799982; 0.000000; 0.599994;,
0.577349; -0.577349; 0.577349;,
-0.799982; 0.000000; 0.599994;,
-0.577349; -0.577349; 0.577349;,
0.577349; -0.577349; 0.577349;,
0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
0.554674; 0.000000; 0.832026;,
-0.707083; 0.000000; 0.707083;,
-0.799982; 0.000000; 0.599994;,
0.554674; 0.000000; 0.832026;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.799982; 0.000000; 0.599994;,
-0.707083; 0.000000; -0.707083;,
-0.554674; 0.000000; -0.832026;,
-0.799982; 0.000000; 0.599994;,
0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; 0.707083;,
0.799982; 0.000000; -0.599994;,
0.707083; 0.000000; 0.707083;,
0.554674; 0.000000; 0.832026;,
0.799982; 0.000000; -0.599994;,
-0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
0.799982; 0.000000; -0.599994;,
-0.707083; 0.000000; -0.707083;,
0.799982; 0.000000; -0.599994;,
-0.554674; 0.000000; -0.832026;,
-0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
0.799982; 0.000000; 0.599994;,
-0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
0.554674; 0.000000; -0.832026;,
0.799982; 0.000000; 0.599994;,
0.707083; 0.000000; -0.707083;,
0.799982; 0.000000; 0.599994;,
0.707083; 0.000000; 0.707083;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
0.554674; 0.000000; -0.832026;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; -0.707083;,
-0.666646; 0.333323; -0.666646;,
-0.333323; 0.666646; 0.666646;,
0.666646; 0.666646; -0.333323;,
-0.333323; 0.666646; 0.666646;,
0.577349; 0.577349; 0.577349;,
0.666646; 0.666646; -0.333323;,
0.799982; 0.000000; 0.599994;,
0.554674; 0.000000; -0.832026;,
0.666646; 0.666646; -0.333323;,
0.799982; 0.000000; 0.599994;,
0.666646; 0.666646; -0.333323;,
0.577349; 0.577349; 0.577349;,
-0.333323; 0.666646; 0.666646;,
-0.666646; 0.333323; -0.666646;,
-0.707083; 0.000000; 0.707083;,
-0.666646; 0.333323; -0.666646;,
-0.707083; 0.000000; -0.707083;,
-0.707083; 0.000000; 0.707083;,
-0.666646; 0.333323; -0.666646;,
0.666646; 0.666646; -0.333323;,
0.554674; 0.000000; -0.832026;,
-0.666646; 0.333323; -0.666646;,
0.554674; 0.000000; -0.832026;,
-0.707083; 0.000000; -0.707083;,
-0.333323; 0.666646; 0.666646;,
-0.707083; 0.000000; 0.707083;,
0.799982; 0.000000; 0.599994;,
-0.333323; 0.666646; 0.666646;,
0.799982; 0.000000; 0.599994;,
0.577349; 0.577349; 0.577349;;
44;
3; 0, 2, 1;,
3; 3, 5, 4;,
3; 6, 8, 7;,
3; 9, 11, 10;,
3; 12, 14, 13;,
3; 15, 17, 16;,
3; 18, 20, 19;,
3; 21, 23, 22;,
3; 24, 26, 25;,
3; 27, 29, 28;,
3; 30, 32, 31;,
3; 33, 35, 34;,
3; 36, 38, 37;,
3; 39, 41, 40;,
3; 42, 44, 43;,
3; 45, 47, 46;,
3; 48, 50, 49;,
3; 51, 53, 52;,
3; 54, 56, 55;,
3; 57, 59, 58;,
3; 60, 62, 61;,
3; 63, 65, 64;,
3; 66, 68, 67;,
3; 69, 71, 70;,
3; 72, 74, 73;,
3; 75, 77, 76;,
3; 78, 80, 79;,
3; 81, 83, 82;,
3; 84, 86, 85;,
3; 87, 89, 88;,
3; 90, 92, 91;,
3; 93, 95, 94;,
3; 96, 98, 97;,
3; 99, 101, 100;,
3; 102, 104, 103;,
3; 105, 107, 106;,
3; 108, 110, 109;,
3; 111, 113, 112;,
3; 114, 116, 115;,
3; 117, 119, 118;,
3; 120, 122, 121;,
3; 123, 125, 124;,
3; 126, 128, 127;,
3; 129, 131, 130;;
}  //End of MeshNormals
MeshTextureCoords {
132;
-0.007812;-0.937500;,
0.468750;-0.695312;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.171875;-0.906250;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.734375;-0.210938;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.171875;-0.906250;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.726562;-0.414062;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.820312;-0.671875;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.468750;-0.695312;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.726562;-0.414062;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.734375;-0.210938;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.023438;-0.968750;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.632812;-0.500000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.453125;-0.945312;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.125000;-0.804688;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.125000;-0.804688;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.914062;-0.015625;,
1.000000;-1.000000;,
0.000000;-0.000000;,
1.000000;-0.000000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.632812;-0.500000;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.914062;-0.015625;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.125000;-0.804688;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.023438;-0.968750;,
1.000000;-1.000000;,
0.000000;-0.000000;,
0.453125;-0.945312;,
1.000000;-1.000000;;
}  //End of MeshTextureCoords

ok, this part I guess I pretty much understand,since I managed to get it implemented correctly :) next up...
  XSkinMeshHeader {
5;
15;
6;
}
SkinWeights {
"Bone_001";
18;
103,
105,
114,
126,
129,
106,
113,
131,
102,
115,
117,
120,
123,
104,
107,
110,
112,
121;
0.033756,
0.033756,
0.033756,
0.033756,
0.033756,
0.029167,
0.029167,
0.029167,
0.049336,
0.049336,
0.049336,
0.049336,
0.049336,
0.032584,
0.032584,
0.032584,
0.032584,
0.032584;
1.000000,0.000000,0.000000,0.000000,
0.000000,0.002400,-1.000000,0.000000,
0.000000,1.000000,0.002400,0.000000,
0.000000,-1.000000,-0.002400,1.000000
}
SkinWeights {
"Bone_002";
0;
1.000000,0.000000,0.000000,0.000000,
0.000000,-0.032100,-0.999500,0.000000,
0.000000,0.999500,-0.032100,0.000000,
0.000000,-2.255200,0.075400,1.000000
}
SkinWeights {
"Bone_003";
132;
103,
105,
114,
126,
129,
79,
81,
84,
116,
119,
127,
78,
91,
93,
108,
111,
128,
130,
106,
113,
131,
102,
115,
117,
120,
123,
85,
87,
96,
99,
118,
125,
90,
97,
109,
122,
124,
104,
107,
110,
112,
121,
54,
57,
67,
69,
88,
101,
55,
60,
92,
95,
98,
100,
61,
63,
72,
80,
83,
94,
66,
73,
75,
82,
86,
89,
31,
33,
36,
68,
71,
76,
30,
43,
45,
64,
74,
77,
37,
39,
48,
51,
59,
70,
42,
49,
56,
58,
62,
65,
7,
12,
15,
44,
47,
50,
52,
6,
9,
19,
40,
53,
13,
24,
32,
35,
46,
18,
21,
25,
27,
34,
38,
41,
2,
5,
14,
16,
26,
29,
0,
23,
28,
1,
3,
11,
20,
22,
4,
8,
10,
17;
0.341596,
0.341596,
0.341596,
0.341596,
0.341596,
0.420363,
0.420363,
0.420363,
0.420363,
0.420363,
0.420363,
0.464187,
0.464187,
0.464187,
0.464187,
0.464187,
0.464187,
0.464187,
0.355773,
0.355773,
0.355773,
0.347670,
0.347670,
0.347670,
0.347670,
0.347670,
0.455057,
0.455057,
0.455057,
0.455057,
0.455057,
0.455057,
0.472454,
0.472454,
0.472454,
0.472454,
0.472454,
0.355873,
0.355873,
0.355873,
0.355873,
0.355873,
0.317348,
0.317348,
0.317348,
0.317348,
0.317348,
0.317348,
0.319257,
0.319257,
0.319257,
0.319257,
0.319257,
0.319257,
0.314616,
0.314616,
0.314616,
0.314616,
0.314616,
0.314616,
0.311477,
0.311477,
0.311477,
0.311477,
0.311477,
0.311477,
0.342739,
0.342739,
0.342739,
0.342739,
0.342739,
0.342739,
0.342436,
0.342436,
0.342436,
0.342436,
0.342436,
0.342436,
0.344942,
0.344942,
0.344942,
0.344942,
0.344942,
0.344942,
0.344508,
0.344508,
0.344508,
0.344508,
0.344508,
0.344508,
0.469669,
0.469669,
0.469669,
0.469669,
0.469669,
0.469669,
0.469669,
0.469530,
0.469530,
0.469530,
0.469530,
0.469530,
0.473440,
0.473440,
0.473440,
0.473440,
0.473440,
0.471819,
0.471819,
0.471819,
0.471819,
0.471819,
0.471819,
0.471819,
0.459076,
0.459076,
0.459076,
0.459076,
0.459076,
0.459076,
0.459859,
0.459859,
0.459859,
0.459713,
0.459713,
0.459713,
0.459713,
0.459713,
0.457383,
0.457383,
0.457383,
0.457383;
1.000000,0.000000,0.000000,0.000000,
0.000000,0.030600,-0.999500,0.000000,
0.000000,0.999500,0.030600,0.000000,
0.000000,-3.510200,-0.144600,1.000000
}
SkinWeights {
"Bone_004";
132;
103,
105,
114,
126,
129,
79,
81,
84,
116,
119,
127,
78,
91,
93,
108,
111,
128,
130,
106,
113,
131,
102,
115,
117,
120,
123,
85,
87,
96,
99,
118,
125,
90,
97,
109,
122,
124,
104,
107,
110,
112,
121,
54,
57,
67,
69,
88,
101,
55,
60,
92,
95,
98,
100,
61,
63,
72,
80,
83,
94,
66,
73,
75,
82,
86,
89,
31,
33,
36,
68,
71,
76,
30,
43,
45,
64,
74,
77,
37,
39,
48,
51,
59,
70,
42,
49,
56,
58,
62,
65,
7,
12,
15,
44,
47,
50,
52,
6,
9,
19,
40,
53,
13,
24,
32,
35,
46,
18,
21,
25,
27,
34,
38,
41,
2,
5,
14,
16,
26,
29,
0,
23,
28,
1,
3,
11,
20,
22,
4,
8,
10,
17;
0.163324,
0.163324,
0.163324,
0.163324,
0.163324,
0.215433,
0.215433,
0.215433,
0.215433,
0.215433,
0.215433,
0.215349,
0.215349,
0.215349,
0.215349,
0.215349,
0.215349,
0.215349,
0.168731,
0.168731,
0.168731,
0.165487,
0.165487,
0.165487,
0.165487,
0.165487,
0.215891,
0.215891,
0.215891,
0.215891,
0.215891,
0.215891,
0.215233,
0.215233,
0.215233,
0.215233,
0.215233,
0.168440,
0.168440,
0.168440,
0.168440,
0.168440,
0.379916,
0.379916,
0.379916,
0.379916,
0.379916,
0.379916,
0.380710,
0.380710,
0.380710,
0.380710,
0.380710,
0.380710,
0.387358,
0.387358,
0.387358,
0.387358,
0.387358,
0.387358,
0.386436,
0.386436,
0.386436,
0.386436,
0.386436,
0.386436,
0.227694,
0.227694,
0.227694,
0.227694,
0.227694,
0.227694,
0.227211,
0.227211,
0.227211,
0.227211,
0.227211,
0.227211,
0.228640,
0.228640,
0.228640,
0.228640,
0.228640,
0.228640,
0.228238,
0.228238,
0.228238,
0.228238,
0.228238,
0.228238,
0.193774,
0.193774,
0.193774,
0.193774,
0.193774,
0.193774,
0.193774,
0.193595,
0.193595,
0.193595,
0.193595,
0.193595,
0.192044,
0.192044,
0.192044,
0.192044,
0.192044,
0.192524,
0.192524,
0.192524,
0.192524,
0.192524,
0.192524,
0.192524,
0.213981,
0.213981,
0.213981,
0.213981,
0.213981,
0.213981,
0.212335,
0.212335,
0.212335,
0.212225,
0.212225,
0.212225,
0.212225,
0.212225,
0.216489,
0.216489,
0.216489,
0.216489;
1.000000,0.000000,0.000000,0.000000,
0.000000,-0.033900,-0.999400,0.000000,
0.000000,0.999400,-0.033900,0.000000,
0.000000,-5.047700,0.181200,1.000000
}
SkinWeights {
"Bone_005";
132;
103,
105,
114,
126,
129,
79,
81,
84,
116,
119,
127,
78,
91,
93,
108,
111,
128,
130,
106,
113,
131,
102,
115,
117,
120,
123,
85,
87,
96,
99,
118,
125,
90,
97,
109,
122,
124,
104,
107,
110,
112,
121,
54,
57,
67,
69,
88,
101,
55,
60,
92,
95,
98,
100,
61,
63,
72,
80,
83,
94,
66,
73,
75,
82,
86,
89,
31,
33,
36,
68,
71,
76,
30,
43,
45,
64,
74,
77,
37,
39,
48,
51,
59,
70,
42,
49,
56,
58,
62,
65,
7,
12,
15,
44,
47,
50,
52,
6,
9,
19,
40,
53,
13,
24,
32,
35,
46,
18,
21,
25,
27,
34,
38,
41,
2,
5,
14,
16,
26,
29,
0,
23,
28,
1,
3,
11,
20,
22,
4,
8,
10,
17;
0.078383,
0.078383,
0.078383,
0.078383,
0.078383,
0.103265,
0.103265,
0.103265,
0.103265,
0.103265,
0.103265,
0.103172,
0.103172,
0.103172,
0.103172,
0.103172,
0.103172,
0.103172,
0.080974,
0.080974,
0.080974,
0.079439,
0.079439,
0.079439,
0.079439,
0.079439,
0.103806,
0.103806,
0.103806,
0.103806,
0.103806,
0.103806,
0.103441,
0.103441,
0.103441,
0.103441,
0.103441,
0.080852,
0.080852,
0.080852,
0.080852,
0.080852,
0.185076,
0.185076,
0.185076,
0.185076,
0.185076,
0.185076,
0.184907,
0.184907,
0.184907,
0.184907,
0.184907,
0.184907,
0.183145,
0.183145,
0.183145,
0.183145,
0.183145,
0.183145,
0.183329,
0.183329,
0.183329,
0.183329,
0.183329,
0.183329,
0.363752,
0.363752,
0.363752,
0.363752,
0.363752,
0.363752,
0.365105,
0.365105,
0.365105,
0.365105,
0.365105,
0.365105,
0.360247,
0.360247,
0.360247,
0.360247,
0.360247,
0.360247,
0.361556,
0.361556,
0.361556,
0.361556,
0.361556,
0.361556,
0.284909,
0.284909,
0.284909,
0.284909,
0.284909,
0.284909,
0.284909,
0.285079,
0.285079,
0.285079,
0.285079,
0.285079,
0.283294,
0.283294,
0.283294,
0.283294,
0.283294,
0.284156,
0.284156,
0.284156,
0.284156,
0.284156,
0.284156,
0.284156,
0.276806,
0.276806,
0.276806,
0.276806,
0.276806,
0.276806,
0.277504,
0.277504,
0.277504,
0.277709,
0.277709,
0.277709,
0.277709,
0.277709,
0.276189,
0.276189,
0.276189,
0.276189;
1.000000,0.000000,0.000000,0.000000,
0.000000,0.058600,-0.998300,0.000000,
0.000000,0.998300,0.058600,0.000000,
0.000000,-6.229900,-0.396800,1.000000
}
SkinWeights {
"Bone_000";
132;
103,
105,
114,
126,
129,
79,
81,
84,
116,
119,
127,
78,
91,
93,
108,
111,
128,
130,
106,
113,
131,
102,
115,
117,
120,
123,
85,
87,
96,
99,
118,
125,
90,
97,
109,
122,
124,
104,
107,
110,
112,
121,
54,
57,
67,
69,
88,
101,
55,
60,
92,
95,
98,
100,
61,
63,
72,
80,
83,
94,
66,
73,
75,
82,
86,
89,
31,
33,
36,
68,
71,
76,
30,
43,
45,
64,
74,
77,
37,
39,
48,
51,
59,
70,
42,
49,
56,
58,
62,
65,
7,
12,
15,
44,
47,
50,
52,
6,
9,
19,
40,
53,
13,
24,
32,
35,
46,
18,
21,
25,
27,
34,
38,
41,
2,
5,
14,
16,
26,
29,
0,
23,
28,
1,
3,
11,
20,
22,
4,
8,
10,
17;
0.382941,
0.382941,
0.382941,
0.382941,
0.382941,
0.260939,
0.260939,
0.260939,
0.260939,
0.260939,
0.260939,
0.217292,
0.217292,
0.217292,
0.217292,
0.217292,
0.217292,
0.217292,
0.365355,
0.365355,
0.365355,
0.358069,
0.358069,
0.358069,
0.358069,
0.358069,
0.225246,
0.225246,
0.225246,
0.225246,
0.225246,
0.225246,
0.208873,
0.208873,
0.208873,
0.208873,
0.208873,
0.362250,
0.362250,
0.362250,
0.362250,
0.362250,
0.117660,
0.117660,
0.117660,
0.117660,
0.117660,
0.117660,
0.115126,
0.115126,
0.115126,
0.115126,
0.115126,
0.115126,
0.114881,
0.114881,
0.114881,
0.114881,
0.114881,
0.114881,
0.118758,
0.118758,
0.118758,
0.118758,
0.118758,
0.118758,
0.065814,
0.065814,
0.065814,
0.065814,
0.065814,
0.065814,
0.065249,
0.065249,
0.065249,
0.065249,
0.065249,
0.065249,
0.066171,
0.066171,
0.066171,
0.066171,
0.066171,
0.066171,
0.065698,
0.065698,
0.065698,
0.065698,
0.065698,
0.065698,
0.051648,
0.051648,
0.051648,
0.051648,
0.051648,
0.051648,
0.051648,
0.051796,
0.051796,
0.051796,
0.051796,
0.051796,
0.051221,
0.051221,
0.051221,
0.051221,
0.051221,
0.051502,
0.051502,
0.051502,
0.051502,
0.051502,
0.051502,
0.051502,
0.050137,
0.050137,
0.050137,
0.050137,
0.050137,
0.050137,
0.050302,
0.050302,
0.050302,
0.050354,
0.050354,
0.050354,
0.050354,
0.050354,
0.049939,
0.049939,
0.049939,
0.049939;
1.000000,0.000000,0.000000,0.000000,
0.000000,0.000000,-1.000000,0.000000,
0.000000,1.000000,0.000000,0.000000,
0.000000,0.000000,0.000000,1.000000
}
}  // End of the Object Cube
}  // End of the Root Frame

ok, I had partial success with this part, I understand that the matrix for every bone "binds" the skeleton to the mesh,(lets call this the binding matrix) and the weights and index affects how much each vertex is binded by a bone. So, I have, for each vertex, (lets say vertexA) newVertexAPosition = (inverseBindingMatrix(Bone_000) * worldMatrix(Bone_000)) * weight(vertexA,Bone_000) * currentPosition(vertexA) + (inverseBindingMatrix(Bone_001) * worldMatrix(Bone_001)) * weight(vertexA,Bone_001) * currentPosition(vertexA) + .... + (inverseBindingMatrix(Bone_005) * worldMatrix(Bone_005)) * weight(vertexA,Bone_005) * currentPosition(vertexA) correct? I'm new to this so please comment if I'm wrong. Basically why I said I only have partial success with this is that the model isn't deformed(or at least doesn't look deformed), but the orientation of the whole model is wrong, any idea where I might have gone wrong? ok, last and the most confusing part for me, animations
AnimationSet AnimationSet0 {
Animation {
{ Bone_001 }
AnimationKey {
4;
3;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,-0.002400,0.000000,0.000000,0.002400,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000;;,
91;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.608200,-0.793800,0.000000,0.000000,0.793800,0.608200,0.000000,0.000000,1.000000,0.000000,1.000000;;,
121;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.626100,0.779700,0.000000,0.000000,-0.779700,0.626100,0.000000,0.000000,1.000000,0.000000,1.000000;;;
}
}

Animation {
{ Bone_002 }
AnimationKey {
4;
1;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.999400,0.034500,0.000000,0.000000,-0.034500,0.999400,0.000000,0.000000,1.256400,0.000000,1.000000;;;
}
}

Animation {
{ Bone_003 }
AnimationKey {
4;
2;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.998000,-0.062600,0.000000,0.000000,0.062600,0.998000,0.000000,0.000000,1.257200,0.000000,1.000000;;,
61;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.820100,-0.572200,0.000000,0.000000,0.572200,0.820100,0.000000,0.000000,1.257200,0.000000,1.000000;;;
}
}

Animation {
{ Bone_004 }
AnimationKey {
4;
1;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.997900,0.064500,0.000000,0.000000,-0.064500,0.997900,0.000000,0.000000,1.538700,0.000000,1.000000;;;
}
}

Animation {
{ Bone_005 }
AnimationKey {
4;
2;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.995700,-0.092500,0.000000,0.000000,0.092500,0.995700,0.000000,0.000000,1.192200,0.000000,1.000000;;,
31;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.635100,-0.772400,0.000000,0.000000,0.772400,0.635100,0.000000,0.000000,1.192200,0.000000,1.000000;;;
}
}

Animation {
{ Bone_000 }
AnimationKey {
4;
1;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,1.000000,0.002400,0.000000,0.000000,-0.002400,1.000000,0.000000,-0.097800,-4.209400,-0.070400,1.000000;;;
}
}

} // End of Animation Set

Ok, first off, from what i understand from the text,
Animation {
{ Bone_005 }
AnimationKey {
4;
2;
1;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.995700,-0.092500,0.000000,0.000000,0.092500,0.995700,0.000000,0.000000,1.192200,0.000000,1.000000;;,
31;16;1.000000,0.000000,0.000000,0.000000,0.000000,0.635100,-0.772400,0.000000,0.000000,0.772400,0.635100,0.000000,0.000000,1.192200,0.000000,1.000000;;;
}
}

Bone_005 will be at 2 keyframed positions at keyframe 1 and 31, and these positions are represented by matrices(lets call these animation matrices). Now the whole crux of this whole post. WHAT DO I DO WITH THE MATRICES? are they the local armatures' positions (represented by matrices) at those keyframes? Or are they transformation matrices which I have to apply on the armatures(the matrices discussed on the very first part of the post) So lets say for keyframe 31, Bone_005, do I 1) Multiply the animationMatrix(Bone_005) with localMatrix(Bone_005), then multiply with the other localMatrices to find the world Matrix, then use the inverseBindingMatrix * worldMatrix * weight * vertex to find all the new individual vertex positions, for all bones binded by Bone_005. or 2) Replace the armature for Bone_005, meaning replace 1.000000,0.000000,0.000000,0.000000, 0.000000,0.995700,-0.092500,0.000000, 0.000000,0.092500,0.995700,0.000000, 0.000000,1.192200,0.000000,1.000000 with .000000,0.000000,0.000000,0.000000,0.000000,0.635100,-0.772400,0.000000,0.000000,0.772400,0.635100,0.000000,0.000000,1.192200,0.000000,1.000000 then multiply it with the other bones to find the worldMatrix then so on... 3) Other ways?!? So, I guess interpolation is complicated too? I touched a bit of it but totally messed the model up, so I decided to get my basics right first. Also, I see that the order of matrix multiplication matters, and this is also something I'm not sure about Yep, so that's about it, whew, long post, thanks for taking your time to read it and help me, I really appreciate it. Also, it might help if you know that I'm using openGL to render the model, but I don't think it would mess the matrices up,(right-handed vs left-handed systems) since I'm using my own matrix calculator and other maths calculators. Once again, thanks alot for your help and time reading this Cheers :)

##### Share on other sites
X File Format Reference -> Text Encoding

Although I should point out that the .X file format really isn't a very nice format for parsing as text. Your life will be much easier if you can use binary instead.

##### Share on other sites
Hi, thanks for taking time to read my problem.

Unfortunately, I'm not using windows and not using directX as an API, I am just using the text file as a medium to represent data which is exported from my 3D modeling software to my code. Therefore, D3DMatrix and other directX related classes or functions would not be used by me.

Basically I can say that I understand what are the information stored in the .x file. what I'm not sure is how to use this information to make an animated model with code.

Thanks again.

##### Share on other sites
Isn't what Evil Steve linked exactly what you want?

This lists all templates and this explains AnimationKey quite well

No-one is asking you to use D3DMatrix..

##### Share on other sites
Quote:
 Original post by charpiUnfortunately, I'm not using windows and not using directX as an API, I am just using the text file as a medium to represent data which is exported from my 3D modeling software to my code. Therefore, D3DMatrix and other directX related classes or functions would not be used by me.
You don't have to use them, but you'll need to know how they work, since they're used by the .X file format.

Quote:
 Original post by charpiBasically I can say that I understand what are the information stored in the .x file. what I'm not sure is how to use this information to make an animated model with code.
The Templates section of the docs covers what each template type is and how it's defined. As for actually applying all of the information to render a model, you might be best trying to find a .X file parser and reverse engineering it. There's some information in each of the template sections, but it's still a bit hard to follow.

The following is fairly guess-y, I've not done much .X file skinned mesh stuff before:

Quote:
 Original post by charpiAm I right to say that these are the representations of the armatures in my model's underlying skeleton? They are each local matrices, right?(Lets call them localMatrix for now) What does rootFrame do? From my guess it isn't a bone, it is just a matrix which we have to multiply against to find the "world matrix", (i'm assuming that these are individual local bone matrices laid out in a hierarchy, correct?)
I believe that's all correct, yes.

Quote:
 Original post by charpiSo, next, in what way do I combine these matrices, is it top to bottom or bottom to top?
I think it's top to bottom - the transforms are hierarchical, so the hand matrix needs transformed by the arm matrix and so on. So to get the hand matrix, you'd do:
Hand = Body * Torso * UpperArm * Arm
And so on.

Quote:
 Original post by charpiSo, I have, for each vertex, (lets say vertexA)newVertexAPosition = (inverseBindingMatrix(Bone_000) * worldMatrix(Bone_000)) * weight(vertexA,Bone_000) * currentPosition(vertexA) + (inverseBindingMatrix(Bone_001) * worldMatrix(Bone_001)) * weight(vertexA,Bone_001) * currentPosition(vertexA) + .... + (inverseBindingMatrix(Bone_005) * worldMatrix(Bone_005)) * weight(vertexA,Bone_005) * currentPosition(vertexA)correct? I'm new to this so please comment if I'm wrong.
Yes. It's just standard skin weights.

Quote:
 Original post by charpiBasically why I said I only have partial success with this is that the model isn't deformed(or at least doesn't look deformed), but the orientation of the whole model is wrong, any idea where I might have gone wrong?
In Direct3D, +Z is "into" the screen, and +Y is "up". I seem to recall that OpenGL has +Z as "out of" the screen, and +Y is up. You'll need to compensate here (Now I think about it, I'm not even sure that Y and Z are the same axes in OpenGL).

Quote:
 Original post by charpiok, last and the most confusing part for me, animations*** Source Snippet Removed ***Ok, first off, from what i understand from the text,*** Source Snippet Removed ***Bone_005 will be at 2 keyframed positions at keyframe 1 and 31, and these positions are represented by matrices(lets call these animation matrices). Now the whole crux of this whole post.WHAT DO I DO WITH THE MATRICES?
See the AnimationKey section and sub-sections.

Quote:
 Original post by charpiAlso, I see that the order of matrix multiplication matters, and this is also something I'm not sure about
If you don't know that the order of matrix multiplications matters, I don't think you should be trying to load a skinned mesh [smile]

##### Share on other sites
ok thanks alot !

Now the only thing is to find out whether the animation matrices replace the worldMatrix of that bone, the local Matrix of that bone, or is it just a transformation matrix which I should apply to the FrameTransformMatrix to get a new matrix as a local/world Matrix...the msdn is quite vague on animation matrices...

thanks alot, will probably be back with much more questions!!

cheers

##### Share on other sites
DirectX matrices are stored in row-major layout. That is, a matrix with the base vectors U, V and W and the translational part T are given in the following format:

Ux Uy Uz 0Vx Vy Vz 0 Wx Wy Wz 0Tx Ty Tz 1

You should be able to decipher the matrices in XFiles using this schema. Every frame states its local tranformation, the transformation of the node in relation to its parent's local coordinate space. Therefore, animations alter the *local* transformation of the node they affect. They replace the node's original transformation matrix, to be more precise.

Bones have an offset matrix each. It's a bit mis-named like this, other sources describe it more accuratly as inverse bone matrix. It's the matrix that transforms from mesh coordinate space to the bone's local coordinate space. Therefore, to get a full bone transformation matrix which describes how a vertex of the mesh is transformed by the bone you have to do the following:

BoneMat = BoneOffsetMatrix * BoneNodeTransform * ParentNodeTransform * ... all the way back to the root node of the bone hierarchy. For row-major matrices the multiplication sequence is MatFirst * MatMiddle * MatLast. This is the opposite sequence of what you might be used to from OpenGL's column-major matrices.

For the moment you can safely ignore the root frame's transformation. In most cases it will be the unity matrix anyways.

At last: please don't mind me posting a bit of a promotion here: Assimp - The Open Asset Import Library. Reads XFiles as well as over 20 other file formats into an in-memory data structure which is pretty easy to use. For XFiles, all three kinds are supported: text, binary and compressed binary. While it might be fun at first to write an model loader, it will be a lot of work in the long run to support all the exporters out there, each with it's own set of bugs you have to work around. And I talk from experience, I'm the developer of the XFile loader of the aforementioned library.

Bye, Thomas

[Edited by - Schrompf on May 18, 2009 1:33:36 PM]

##### Share on other sites
Hey thanks. I will go and try out your methods. Will get back here if i encounter any more problems. Thanks again to all who have helped.

1. 1
2. 2
3. 3
4. 4
frob
15
5. 5

• 12
• 12
• 20
• 12
• 13
• ### Forum Statistics

• Total Topics
632149
• Total Posts
3004453

×


text:
# CDF of conditional distribution

Suppose that $X$ and $Y$ are iid normally distributed and $a$ is a scalar. What is $\Pr(Y+aX<0 | X>0)$?

-
Sorry about that -- I clarified that they're jointly normal. –  ABC Jul 26 '12 at 3:58
Try this paper: etrij.etri.re.kr/Cyber/servlet/… –  Douglas Zare Jul 26 '12 at 5:44
Transform $(X,Y)\rightarrow (X,Z)$, where $Z=Y+aX$; you will obtain that $(X,Z)$ has a bivariate normal distribution with a certain mean and covariance matrix. Then use the definition ${\mathbb P}(Y+aX<0\vert X>0)=\dfrac{{\mathbb P}(Y+aX<0,X>0)}{{\mathbb P}(X>0)}=\dfrac{{\mathbb P}(Z<0,X>0)}{{\mathbb P}(X>0)}$. The numerator can be calculated using the CDF of a bivariate normal and the denominator using the CDF of the univariate normal. –  user10525 Jul 26 '12 at 9:37
If the means are zero, this requires (virtually) no calculation at all. Are you interested in the general case or, perhaps, this specific one? –  cardinal Jul 26 '12 at 13:12
@cardinal I guess the OP is interested in the general case because this expression appears in the paper mentioned in the previous question. I also guess he did not mean i.i.d.. –  user10525 Jul 26 '12 at 13:20

format: plain


text:
# Preparing survey data for analysis

I am preparing a complex survey data for analysis. The survey involved a two-stage stratified cluster sampling. In the first stage, I have 7 strata and 14 sampling units and in the second stage I have 13 strata and 29 sampling units. I have made sure that there are at least 2 sampling units per sampling stratum. However, after declaring the survey design in Stata, the svydescribe command yields strata that are duplicates of already existing strata but with single units. The following table depicts the Stata output after submitting the command svydescribe, final.

As can be seen from the table, in the second stage of sampling, unit/cluster 7 belongs to stratum 4. However, one observation which belongs to the same stratum and unit/cluster has been considered as belonging to a different stratum and unit/cluster. The same holds with stratum 7 and several other strata. What causes such problems and how are they handled?

Update: after serially issuing the commands

egen _svy_tag = tag( PSEUDOPSU PSUSTRATA SSU PSEUDOSSUST FPC1 FPC2), missing
replace _svy_tag = _svy_tag | missing(NWEIGHT)
list PSEUDOPSU PSUSTRATA SSU PSEUDOSSUST FPC1 FPC2 NWEIGHT if _svy_tag

as suggested by StasK in his comment below, I obtained the following output.

• I'm not sure this is on-topic, but anyway, you should include the exact commands you issued and exact output. A complete, reproducible example, is even better. Aug 20 '14 at 16:41
• This is the command I issued: svyset PSEUDOPSU [pweight=NWEIGHT], strata( PSUSTRATA) fpc(FPC1) || SSU, strata( PSEUDOSSUST) fpc(FPC2). Subsequently, I issued the command 'svydescribe, final'. [I cannot include the output due to limitation of number of characters for comments on this site.] In the output I see several duplicate strata with single units where as in the actual dataset there are no strata with single units. Aug 21 '14 at 6:18
• Do not use the comment section to give additional information that is not suited for this section. Use the edit button to edit your original post. Aug 21 '14 at 11:53
• egen _svy_tag = tag( PSEUDOPSU PSUSTRATA SSU PSEUDOSSUST FPC1 FPC2), missing [ENTER] replace _svy_tag = _svy_tag | missing(NWEIGHT) [ENTER] list PSEUDOPSU PSUSTRATA SSU PSEUDOSSUST FPC1 FPC2 NWEIGHT if _svy_tag [ENTER] and add the output to your original post. (+1 to Roberto: this is a live website where you can edit a lot of stuff -- you can certainly edit your own posts). Aug 21 '14 at 14:45
• The problems are obviously in your code that creates the survey variables from whatever you obtained from the field. You'd have to review and resolve the offending units that must have been mislabeled. Aug 21 '14 at 14:48

i believe you might be looking for the stata option singleunit(centered) ?

the cdc has a thorough description of this issue and how to deal with it programmatically in different statistical languages

http://www.cdc.gov/nchs/nhis/singleton_psu.htm

the R survey package also has a good succinct page on the subject

http://r-survey.r-forge.r-project.org/survey/exmample-lonely.html

• Actually I don't have strata with single units. For strata with single units, I have created pseudostrata by merging them with adjacent strata. Now no stratum contains a single unit in my dataset. However, after declaring the survey design using 'svyset' the 'svydescribe' command returns some strata that contain single units. The strata with single units are just duplicates of already existing strata except that they contain single units as I indicated in my initial post. Aug 21 '14 at 6:29
• @user52898 are you sure everything's been recoded properly? i'd be surprised if svydescribe prints duplicates as you've shown. check tab [stratum] and make sure you don't have a stratum "17" and another " 17" or something like that Aug 21 '14 at 7:13
• @ Anthony Damico, I have checked tab [stratum] and tab [clusters]. I also have checked a cross-tabulation of stratum vs cluster. Everything is fine there. Unfortunately due to space limitations, I couldn't include the tab outputs here. Aug 21 '14 at 12:04


text:
# Elements of $$\ZZ/n\ZZ$$¶

An element of the integers modulo $$n$$.

There are three types of integer_mod classes, depending on the size of the modulus.

• IntegerMod_int stores its value in a int_fast32_t (typically an int); this is used if the modulus is less than $$\sqrt{2^{31}-1}$$.
• IntegerMod_int64 stores its value in a int_fast64_t (typically a long long); this is used if the modulus is less than $$2^{31}-1$$. In many places, we assume that the values and the modulus actually fit inside an unsigned long.
• IntegerMod_gmp stores its value in a mpz_t; this can be used for an arbitrarily large modulus.

All extend IntegerMod_abstract.

For efficiency reasons, it stores the modulus (in all three forms, if possible) in a common (cdef) class NativeIntStruct rather than in the parent.

AUTHORS:

• Robert Bradshaw: most of the work
• Didier Deshommes: bit shifting
• William Stein: editing and polishing; new arith architecture
• Robert Bradshaw: implement native is_square and square_root
• William Stein: sqrt
• Maarten Derickx: moved the valuation code from the global valuation function to here
class sage.rings.finite_rings.integer_mod.Int_to_IntegerMod

EXAMPLES:

We make sure it works for every type.

sage: from sage.rings.finite_rings.integer_mod import Int_to_IntegerMod
sage: Rs = [Integers(2**k) for k in range(1,50,10)]
sage: [type(R(0)) for R in Rs]
[<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>]
sage: fs = [Int_to_IntegerMod(R) for R in Rs]
sage: [f(-1) for f in fs]
[1, 2047, 2097151, 2147483647, 2199023255551]

sage.rings.finite_rings.integer_mod.IntegerMod(parent, value)

Create an integer modulo $$n$$ with the given parent.

This is mainly for internal use.

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod import IntegerMod
sage: R = IntegerModRing(100)
sage: type(R._pyx_order.table)
<type 'list'>
sage: IntegerMod(R, 42)
42
sage: IntegerMod(R, 142)
42
sage: IntegerMod(R, 10^100 + 42)
42
sage: IntegerMod(R, -9158)
42

class sage.rings.finite_rings.integer_mod.IntegerMod_abstract

EXAMPLES:

sage: a = Mod(10, 30^10); a
10
sage: type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
sage: loads(a.dumps()) == a
True

additive_order()

Returns the additive order of self.

This is the same as self.order().

EXAMPLES:

sage: Integers(20)(2).additive_order()
10
20
45154201192451

centerlift(*args, **kwds)

Deprecated: Use lift_centered() instead. See trac ticket #15804 for details.

charpoly(var='x')

Returns the characteristic polynomial of this element.

EXAMPLES:

sage: k = GF(3)
sage: a = k.gen()
sage: a.charpoly('x')
x + 2
sage: a + 2
0

AUTHORS:

• Craig Citro
crt(other)

Use the Chinese Remainder Theorem to find an element of the integers modulo the product of the moduli that reduces to self and to other. The modulus of other must be coprime to the modulus of self.

EXAMPLES:

sage: a = mod(3,5)
sage: b = mod(2,7)
sage: a.crt(b)
23

sage: a = mod(37,10^8)
sage: b = mod(9,3^8)
sage: a.crt(b)
125900000037

sage: b = mod(0,1)
sage: a.crt(b) == a
True
sage: a.crt(b).modulus()
100000000

AUTHORS:

divides(other)

Test wheter self divides other.

EXAMPLES:

sage: R = Zmod(6)
sage: R(2).divides(R(4))
True
sage: R(4).divides(R(2))
True
sage: R(2).divides(R(3))
False

generalised_log()

Return integers $$[n_1, \ldots, n_d]$$ such that

$\prod_{i=1}^d x_i^{n_i} = \text{self},$

where $$x_1, \dots, x_d$$ are the generators of the unit group returned by self.parent().unit_gens().

EXAMPLES:

sage: m = Mod(3, 1568)
sage: v = m.generalised_log(); v
[1, 3, 1]
sage: prod([Zmod(1568).unit_gens()[i] ** v[i] for i in [0..2]])
3

The method log().

Warning

The output is given relative to the set of generators obtained by passing algorithm='sage' to the method unit_gens() of the parent (which is the default). Specifying algorithm='pari' usually yields a different set of generators that is incompatible with this method.

is_nilpotent()

Return True if self is nilpotent, i.e., some power of self is zero.

EXAMPLES:

sage: a = Integers(90384098234^3)
sage: factor(a.order())
2^3 * 191^3 * 236607587^3
sage: b = a(2*191)
sage: b.is_nilpotent()
False
sage: b = a(2*191*236607587)
sage: b.is_nilpotent()
True

ALGORITHM: Let $$m \geq \log_2(n)$$, where $$n$$ is the modulus. Then $$x \in \ZZ/n\ZZ$$ is nilpotent if and only if $$x^m = 0$$.

PROOF: This is clear if you reduce to the prime power case, which you can do via the Chinese Remainder Theorem.

We could alternatively factor $$n$$ and check to see if the prime divisors of $$n$$ all divide $$x$$. This is asymptotically slower :-).

is_one()
is_primitive_root()

Determines whether this element generates the group of units modulo n.

This is only possible if the group of units is cyclic, which occurs if n is 2, 4, a power of an odd prime or twice a power of an odd prime.

EXAMPLES:

sage: mod(1,2).is_primitive_root()
True
sage: mod(3,4).is_primitive_root()
True
sage: mod(2,7).is_primitive_root()
False
sage: mod(3,98).is_primitive_root()
True
sage: mod(11,1009^2).is_primitive_root()
True

is_square()

EXAMPLES:

sage: Mod(3,17).is_square()
False
sage: Mod(9,17).is_square()
True
sage: Mod(9,17*19^2).is_square()
True
sage: Mod(-1,17^30).is_square()
True
sage: Mod(1/9, next_prime(2^40)).is_square()
True
sage: Mod(1/25, next_prime(2^90)).is_square()
True

ALGORITHM: Calculate the Jacobi symbol $$(\mathtt{self}/p)$$ at each prime $$p$$ dividing $$n$$. It must be 1 or 0 for each prime, and if it is 0 mod $$p$$, where $$p^k || n$$, then $$ord_p(\mathtt{self})$$ must be even or greater than $$k$$.

The case $$p = 2$$ is handled separately.

AUTHORS:

is_unit()
lift_centered()

Lift self to a centered congruent integer.

OUTPUT:

The unique integer $$i$$ such that $$-n/2 < i \leq n/2$$ and $$i = self \mod n$$ (where $$n$$ denotes the modulus).

EXAMPLES:

sage: Mod(0,5).lift_centered()
0
sage: Mod(1,5).lift_centered()
1
sage: Mod(2,5).lift_centered()
2
sage: Mod(3,5).lift_centered()
-2
sage: Mod(4,5).lift_centered()
-1
sage: Mod(50,100).lift_centered()
50
sage: Mod(51,100).lift_centered()
-49
sage: Mod(-1,3^100).lift_centered()
-1

log(b=None, logarithm_exists=False)

Return an integer $$x$$ such that $$b^x = a$$, where $$a$$ is self.

INPUT:

• self - unit modulo $$n$$
• b - a unit modulo $$n$$. If b is not given, R.multiplicative_generator() is used, where R is the parent of self.
• logarithm_exists - a boolean (default False). If True it assumes that the logarithm exists in order to speed up the computation, the code might end up in an infinite loop if this is set to True but the logarithm does not exist.

OUTPUT: Integer $$x$$ such that $$b^x = a$$, if this exists; a ValueError otherwise.

Note

If the modulus is prime and b is a generator, this calls Pari’s znlog function, which is rather fast. If not, it falls back on the generic discrete log implementation in sage.groups.generic.discrete_log().

EXAMPLES:

sage: r = Integers(125)
sage: b = r.multiplicative_generator()^3
sage: a = b^17
sage: a.log(b)
17
sage: a.log()
51

A bigger example:

sage: FF = FiniteField(2^32+61)
sage: c = FF(4294967356)
sage: x = FF(2)
sage: a = c.log(x)
sage: a
2147483678
sage: x^a
4294967356

Things that can go wrong. E.g., if the base is not a generator for the multiplicative group, or not even a unit.

sage: Mod(3, 7).log(Mod(2, 7))
Traceback (most recent call last):
...
ValueError: No discrete log of 3 found to base 2 modulo 7
sage: a = Mod(16, 100); b = Mod(4,100)
sage: a.log(b)
Traceback (most recent call last):
...
ValueError: logarithm of 16 is not defined since it is not a unit modulo 100

AUTHORS:

• David Joyner and William Stein (2005-11)
• William Stein (2007-01-27): update to use PARI as requested by David Kohel.
• Simon King (2010-07-07): fix a side effect on PARI
minimal_polynomial(var='x')

Returns the minimal polynomial of this element.

EXAMPLES:
sage: GF(241, ‘a’)(1).minimal_polynomial(var = ‘z’) z + 240
minpoly(var='x')

Returns the minimal polynomial of this element.

EXAMPLES:
sage: GF(241, ‘a’)(1).minpoly() x + 240
modulus()

EXAMPLES:

sage: Mod(3,17).modulus()
17

multiplicative_order()

Returns the multiplicative order of self.

EXAMPLES:

sage: Mod(-1,5).multiplicative_order()
2
sage: Mod(1,5).multiplicative_order()
1
sage: Mod(0,5).multiplicative_order()
Traceback (most recent call last):
...
ArithmeticError: multiplicative order of 0 not defined since it is not a unit modulo 5

norm()

Returns the norm of this element, which is itself. (This is here for compatibility with higher order finite fields.)

EXAMPLES:

sage: k = GF(691)
sage: a = k(389)
sage: a.norm()
389

AUTHORS:

• Craig Citro
nth_root(n, extend=False, all=False, algorithm=None, cunningham=False)

Returns an $$n$$th root of self.

INPUT:

• n - integer $$\geq 1$$
• extend - bool (default: True); if True, return an nth root in an extension ring, if necessary. Otherwise, raise a ValueError if the root is not in the base ring. Warning: this option is not implemented!
• all - bool (default: False); if True, return all $$n$$th roots of self, instead of just one.
• algorithm - string (default: None); The algorithm for the prime modulus case. CRT and p-adic log techniques are used to reduce to this case. ‘Johnston’ is the only currently supported option.
• cunningham - bool (default: False); In some cases, factorization of n is computed. If cunningham is set to True, the factorization of n is computed using trial division for all primes in the so called Cunningham table. Refer to sage.rings.factorint.factor_cunningham for more information. You need to install an optional package to use this method, this can be done with the following command line sage -i cunningham_tables

OUTPUT:

If self has an $$n$$th root, returns one (if all is False) or a list of all of them (if all is True). Otherwise, raises a ValueError (if extend is False) or a NotImplementedError (if extend is True).

Warning

The ‘extend’ option is not implemented (yet).

NOTES:

• If $$n = 0$$:
• if all=True:
• if self=1: all nonzero elements of the parent are returned in a list. Note that this could be very expensive for large parents.
• otherwise: an empty list is returned
• if all=False:
• if self=1: self is returned
• otherwise; a ValueError is raised
• If $$n < 0$$:
• if self is invertible, the $$(-n)$$th root of the inverse of self is returned
• otherwise a ValueError is raised or empty list returned.

EXAMPLES:

sage: K = GF(31)
sage: a = K(22)
sage: K(22).nth_root(7)
13
sage: K(25).nth_root(5)
5
sage: K(23).nth_root(3)
29
sage: mod(225,2^5*3^2).nth_root(4, all=True)
[225, 129, 33, 63, 255, 159, 9, 201, 105, 279, 183, 87, 81, 273, 177, 207, 111, 15, 153, 57, 249, 135, 39, 231]
sage: mod(275,2^5*7^4).nth_root(7, all=True)
[58235, 25307, 69211, 36283, 3355, 47259, 14331]
sage: mod(1,8).nth_root(2,all=True)
[1, 7, 5, 3]
sage: mod(4,8).nth_root(2,all=True)
[2, 6]
sage: mod(1,16).nth_root(4,all=True)
[1, 15, 13, 3, 9, 7, 5, 11]
sage: (mod(22,31)^200).nth_root(200)
5
sage: mod(3,6).nth_root(0,all=True)
[]
sage: mod(3,6).nth_root(0)
Traceback (most recent call last):
...
ValueError
sage: mod(1,6).nth_root(0,all=True)
[1, 2, 3, 4, 5]

ALGORITHMS:

• The default for prime modulus is currently an algorithm described in the following paper:

Johnston, Anna M. A generalized qth root algorithm. Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms. Baltimore, 1999: pp 929-930.

AUTHORS:

• David Roe (2010-2-13)
polynomial(var='x')

Returns a constant polynomial representing this value.

EXAMPLES:

sage: k = GF(7)
sage: a = k.gen(); a
1
sage: a.polynomial()
1
sage: type(a.polynomial())
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

rational_reconstruction()

Use rational reconstruction to try to find a lift of this element to the rational numbers.

EXAMPLES:

sage: R = IntegerModRing(97)
sage: a = R(2) / R(3)
sage: a
33
sage: a.rational_reconstruction()
2/3

This method is also inherited by prime finite fields elements:

sage: k = GF(97)
sage: a = k(RationalField()('2/3'))
sage: a
33
sage: a.rational_reconstruction()
2/3

sqrt(extend=True, all=False)

Returns square root or square roots of self modulo $$n$$.

INPUT:

• extend - bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square root is not in the base ring.
• all - bool (default: False); if True, return {all} square roots of self, instead of just one.

ALGORITHM: Calculates the square roots mod $$p$$ for each of the primes $$p$$ dividing the order of the ring, then lifts them $$p$$-adically and uses the CRT to find a square root mod $$n$$.

See also square_root_mod_prime_power and square_root_mod_prime (in this module) for more algorithmic details.

EXAMPLES:

sage: mod(-1, 17).sqrt()
4
sage: mod(5, 389).sqrt()
86
sage: mod(7, 18).sqrt()
5
sage: a = mod(14, 5^60).sqrt()
sage: a*a
14
sage: mod(15, 389).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2)
9
sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2)
25

sage: a = Mod(3,5); a
3
sage: x = Mod(-1, 360)
sage: x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: y = x.sqrt(); y
sqrt359
sage: y.parent()
Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1
sage: y^2
359

We compute all square roots in several cases:

sage: R = Integers(5*2^3*3^2); R
Ring of integers modulo 360
sage: R(40).sqrt(all=True)
[20, 160, 200, 340]
sage: [x for x in R if x^2 == 40]  # Brute force verification
[20, 160, 200, 340]
sage: R(1).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
sage: R(0).sqrt(all=True)
[0, 60, 120, 180, 240, 300]

sage: R = Integers(5*13^3*37); R
Ring of integers modulo 406445
sage: v = R(-1).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
sage: [x^2 for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
sage: all([x^2==169 for x in v])
True

sage: t = FiniteField(next_prime(2^100))(4)
sage: t.sqrt(extend = False, all = True)
[2, 1267650600228229401496703205651]
sage: t = FiniteField(next_prime(2^100))(2)
sage: t.sqrt(extend = False, all = True)
[]

Modulo a power of 2:

sage: R = Integers(2^7); R
Ring of integers modulo 128
sage: a = R(17)
sage: a.sqrt()
23
sage: a.sqrt(all=True)
[23, 41, 87, 105]
sage: [x for x in R if x^2==17]
[23, 41, 87, 105]

square_root(extend=True, all=False)

Returns square root or square roots of self modulo $$n$$.

INPUT:

• extend - bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square root is not in the base ring.
• all - bool (default: False); if True, return {all} square roots of self, instead of just one.

ALGORITHM: Calculates the square roots mod $$p$$ for each of the primes $$p$$ dividing the order of the ring, then lifts them $$p$$-adically and uses the CRT to find a square root mod $$n$$.

See also square_root_mod_prime_power and square_root_mod_prime (in this module) for more algorithmic details.

EXAMPLES:

sage: mod(-1, 17).sqrt()
4
sage: mod(5, 389).sqrt()
86
sage: mod(7, 18).sqrt()
5
sage: a = mod(14, 5^60).sqrt()
sage: a*a
14
sage: mod(15, 389).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2)
9
sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2)
25

sage: a = Mod(3,5); a
3
sage: x = Mod(-1, 360)
sage: x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: y = x.sqrt(); y
sqrt359
sage: y.parent()
Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1
sage: y^2
359

We compute all square roots in several cases:

sage: R = Integers(5*2^3*3^2); R
Ring of integers modulo 360
sage: R(40).sqrt(all=True)
[20, 160, 200, 340]
sage: [x for x in R if x^2 == 40]  # Brute force verification
[20, 160, 200, 340]
sage: R(1).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
sage: R(0).sqrt(all=True)
[0, 60, 120, 180, 240, 300]

sage: R = Integers(5*13^3*37); R
Ring of integers modulo 406445
sage: v = R(-1).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
sage: [x^2 for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
sage: all([x^2==169 for x in v])
True

sage: t = FiniteField(next_prime(2^100))(4)
sage: t.sqrt(extend = False, all = True)
[2, 1267650600228229401496703205651]
sage: t = FiniteField(next_prime(2^100))(2)
sage: t.sqrt(extend = False, all = True)
[]

Modulo a power of 2:

sage: R = Integers(2^7); R
Ring of integers modulo 128
sage: a = R(17)
sage: a.sqrt()
23
sage: a.sqrt(all=True)
[23, 41, 87, 105]
sage: [x for x in R if x^2==17]
[23, 41, 87, 105]

trace()

Returns the trace of this element, which is itself. (This is here for compatibility with higher order finite fields.)

EXAMPLES:

sage: k = GF(691)
sage: a = k(389)
sage: a.trace()
389

AUTHORS:

• Craig Citro
valuation(p)

The largest power r such that m is in the ideal generated by p^r or infinity if there is not a largest such power. However it is an error to take the valuation with respect to a unit.

Note

This is not a valuation in the mathematical sense. As shown with the examples below.

EXAMPLES:

This example shows that the (a*b).valuation(n) is not always the same as a.valuation(n) + b.valuation(n)

sage: R=ZZ.quo(9)
sage: a=R(3)
sage: b=R(6)
sage: a.valuation(3)
1
sage: a.valuation(3) + b.valuation(3)
2
sage: (a*b).valuation(3)
+Infinity

The valuation with respect to a unit is an error

sage: a.valuation(4)
Traceback (most recent call last):
...
ValueError: Valuation with respect to a unit is not defined.

class sage.rings.finite_rings.integer_mod.IntegerMod_gmp

Elements of $$\ZZ/n\ZZ$$ for n not small enough to be operated on in word size.

AUTHORS:

• Robert Bradshaw (2006-08-24)
gcd(other)

Greatest common divisor

Returns the “smallest” generator in $$\ZZ / N\ZZ$$ of the ideal generated by self and other.

INPUT:

• other – an element of the same ring as this one.

EXAMPLES:

sage: mod(2^3*3^2*5, 3^3*2^2*17^8).gcd(mod(2^4*3*17, 3^3*2^2*17^8))
12
sage: mod(0,17^8).gcd(mod(0,17^8))
0

is_one()

Returns True if this is $$1$$, otherwise False.

EXAMPLES:

sage: mod(1,5^23).is_one()
True
sage: mod(0,5^23).is_one()
False

is_unit()

Return True iff this element is a unit.

EXAMPLES:

sage: mod(13, 5^23).is_unit()
True
sage: mod(25, 5^23).is_unit()
False

lift()

Lift an integer modulo $$n$$ to the integers.

EXAMPLES:

sage: a = Mod(8943, 2^70); type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
sage: lift(a)
8943
sage: a.lift()
8943

class sage.rings.finite_rings.integer_mod.IntegerMod_hom
class sage.rings.finite_rings.integer_mod.IntegerMod_int

Elements of $$\ZZ/n\ZZ$$ for n small enough to be operated on in 32 bits

AUTHORS:

• Robert Bradshaw (2006-08-24)

EXAMPLES:

sage: a = Mod(10,30); a
10
sage: loads(a.dumps()) == a
True

gcd(other)

Greatest common divisor

Returns the “smallest” generator in $$\ZZ / N\ZZ$$ of the ideal generated by self and other.

INPUT:

• other – an element of the same ring as this one.

EXAMPLES:

sage: R = Zmod(60); S = Zmod(72)
sage: a = R(40).gcd(S(30)); a
2
sage: a.parent()
Ring of integers modulo 12
sage: b = R(17).gcd(60); b
1
sage: b.parent()
Ring of integers modulo 60

sage: mod(72*5, 3^3*2^2*17^2).gcd(mod(48*17, 3^3*2^2*17^2))
12
sage: mod(0,1).gcd(mod(0,1))
0

is_one()

Returns True if this is $$1$$, otherwise False.

EXAMPLES:

sage: mod(6,5).is_one()
True
sage: mod(0,5).is_one()
False
sage: mod(1, 1).is_one()
True
sage: Zmod(1).one().is_one()
True

is_unit()

Return True iff this element is a unit

EXAMPLES:

sage: a=Mod(23,100)
sage: a.is_unit()
True
sage: a=Mod(24,100)
sage: a.is_unit()
False

lift()

Lift an integer modulo $$n$$ to the integers.

EXAMPLES:

sage: a = Mod(8943, 2^10); type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
sage: lift(a)
751
sage: a.lift()
751

sqrt(extend=True, all=False)

Returns square root or square roots of self modulo $$n$$.

INPUT:

• extend - bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square root is not in the base ring.
• all - bool (default: False); if True, return {all} square roots of self, instead of just one.

ALGORITHM: Calculates the square roots mod $$p$$ for each of the primes $$p$$ dividing the order of the ring, then lifts them $$p$$-adically and uses the CRT to find a square root mod $$n$$.

See also square_root_mod_prime_power and square_root_mod_prime (in this module) for more algorithmic details.

EXAMPLES:

sage: mod(-1, 17).sqrt()
4
sage: mod(5, 389).sqrt()
86
sage: mod(7, 18).sqrt()
5
sage: a = mod(14, 5^60).sqrt()
sage: a*a
14
sage: mod(15, 389).sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: Mod(1/9, next_prime(2^40)).sqrt()^(-2)
9
sage: Mod(1/25, next_prime(2^90)).sqrt()^(-2)
25

sage: a = Mod(3,5); a
3
sage: x = Mod(-1, 360)
sage: x.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: self must be a square
sage: y = x.sqrt(); y
sqrt359
sage: y.parent()
Univariate Quotient Polynomial Ring in sqrt359 over Ring of integers modulo 360 with modulus x^2 + 1
sage: y^2
359

We compute all square roots in several cases:

sage: R = Integers(5*2^3*3^2); R
Ring of integers modulo 360
sage: R(40).sqrt(all=True)
[20, 160, 200, 340]
sage: [x for x in R if x^2 == 40]  # Brute force verification
[20, 160, 200, 340]
sage: R(1).sqrt(all=True)
[1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359]
sage: R(0).sqrt(all=True)
[0, 60, 120, 180, 240, 300]
sage: GF(107)(0).sqrt(all=True)
[0]

sage: R = Integers(5*13^3*37); R
Ring of integers modulo 406445
sage: v = R(-1).sqrt(all=True); v
[78853, 111808, 160142, 193097, 213348, 246303, 294637, 327592]
sage: [x^2 for x in v]
[406444, 406444, 406444, 406444, 406444, 406444, 406444, 406444]
sage: v = R(169).sqrt(all=True); min(v), -max(v), len(v)
(13, 13, 104)
sage: all([x^2==169 for x in v])
True

Modulo a power of 2:

sage: R = Integers(2^7); R
Ring of integers modulo 128
sage: a = R(17)
sage: a.sqrt()
23
sage: a.sqrt(all=True)
[23, 41, 87, 105]
sage: [x for x in R if x^2==17]
[23, 41, 87, 105]

class sage.rings.finite_rings.integer_mod.IntegerMod_int64

Elements of $$\ZZ/n\ZZ$$ for n small enough to be operated on in 64 bits

EXAMPLES:

sage: a = Mod(10,3^10); a
10
sage: type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>
sage: loads(a.dumps()) == a
True
sage: Mod(5, 2^31)
5

AUTHORS:

• Robert Bradshaw (2006-09-14)
gcd(other)

Greatest common divisor

Returns the “smallest” generator in $$\ZZ / N\ZZ$$ of the ideal generated by self and other.

INPUT:

• other – an element of the same ring as this one.

EXAMPLES:

sage: mod(2^3*3^2*5, 3^3*2^2*17^5).gcd(mod(2^4*3*17, 3^3*2^2*17^5))
12
sage: mod(0,17^5).gcd(mod(0,17^5))
0

is_one()

Returns True if this is $$1$$, otherwise False.

EXAMPLES:

sage: (mod(-1,5^10)^2).is_one()
True
sage: mod(0,5^10).is_one()
False

is_unit()

Return True iff this element is a unit.

EXAMPLES:

sage: mod(13, 5^10).is_unit()
True
sage: mod(25, 5^10).is_unit()
False

lift()

Lift an integer modulo $$n$$ to the integers.

EXAMPLES:

sage: a = Mod(8943, 2^25); type(a)
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>
sage: lift(a)
8943
sage: a.lift()
8943

class sage.rings.finite_rings.integer_mod.IntegerMod_to_Integer

Map to lift elements to Integer.

EXAMPLES:

sage: ZZ.convert_map_from(GF(2))
Lifting map:
From: Finite Field of size 2
To:   Integer Ring

class sage.rings.finite_rings.integer_mod.IntegerMod_to_IntegerMod

Very fast IntegerMod to IntegerMod homomorphism.

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod import IntegerMod_to_IntegerMod
sage: Rs = [Integers(3**k) for k in range(1,30,5)]
sage: [type(R(0)) for R in Rs]
[<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>]
sage: fs = [IntegerMod_to_IntegerMod(S, R) for R in Rs for S in Rs if S is not R and S.order() > R.order()]
sage: all([f(-1) == f.codomain()(-1) for f in fs])
True
sage: [f(-1) for f in fs]
[2, 2, 2, 2, 2, 728, 728, 728, 728, 177146, 177146, 177146, 43046720, 43046720, 10460353202]

is_injective()

Return whether this morphism is injective.

EXAMPLES:

sage: Zmod(4).hom(Zmod(2)).is_injective()
False

is_surjective()

Return whether this morphism is surjective.

EXAMPLES:

sage: Zmod(4).hom(Zmod(2)).is_surjective()
True

class sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod

Fast $$\ZZ \rightarrow \ZZ/n\ZZ$$ morphism.

EXAMPLES:

We make sure it works for every type.

sage: from sage.rings.finite_rings.integer_mod import Integer_to_IntegerMod
sage: Rs = [Integers(10), Integers(10^5), Integers(10^10)]
sage: [type(R(0)) for R in Rs]
[<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>, <type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>]
sage: fs = [Integer_to_IntegerMod(R) for R in Rs]
sage: [f(-1) for f in fs]
[9, 99999, 9999999999]

is_injective()

Return whether this morphism is injective.

EXAMPLES:

sage: ZZ.hom(Zmod(2)).is_injective()
False

is_surjective()

Return whether this morphism is surjective.

EXAMPLES:

sage: ZZ.hom(Zmod(2)).is_surjective()
True

section()
sage.rings.finite_rings.integer_mod.Mod(n, m, parent=None)

Return the equivalence class of $$n$$ modulo $$m$$ as an element of $$\ZZ/m\ZZ$$.

EXAMPLES:

sage: x = Mod(12345678, 32098203845329048)
sage: x
12345678
sage: x^100
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

Illustrates that trac ticket #5971 is fixed. Consider $$n$$ modulo $$m$$ when $$m = 0$$. Then $$\ZZ/0\ZZ$$ is isomorphic to $$\ZZ$$ so $$n$$ modulo $$0$$ is equivalent to $$n$$ for any integer value of $$n$$:

sage: Mod(10, 0)
10
sage: a = randint(-100, 100)
sage: Mod(a, 0) == a
True

class sage.rings.finite_rings.integer_mod.NativeIntStruct

Bases: object

We store the various forms of the modulus here rather than in the parent for efficiency reasons.

We may also store a cached table of all elements of a given ring in this class.

inverses
precompute_table(parent)

Function to compute and cache all elements of this class.

If inverses == True, also computes and caches the inverses of the invertible elements.

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod import NativeIntStruct
sage: R = IntegerModRing(10)
sage: M = NativeIntStruct(R.order())
sage: M.precompute_table(R)
sage: M.table
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: M.inverses
[None, 1, None, 7, None, None, None, 3, None, 9]

This is used by the sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic constructor:

sage: from sage.rings.finite_rings.integer_mod_ring import IntegerModRing_generic
sage: R = IntegerModRing_generic(39, cache=False)
sage: R(5)^-1
8
sage: R(5)^-1 is R(8)
False
sage: R = IntegerModRing_generic(39, cache=True)  # indirect doctest
sage: R(5)^-1 is R(8)
True

Check that the inverse of 0 modulo 1 works, see trac ticket #13639:

sage: R = IntegerModRing_generic(1, cache=True)  # indirect doctest
sage: R(0)^-1 is R(0)
True

table
sage.rings.finite_rings.integer_mod.is_IntegerMod(x)

Return True if and only if x is an integer modulo $$n$$.

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod import is_IntegerMod
sage: is_IntegerMod(5)
False
sage: is_IntegerMod(Mod(5,10))
True

sage.rings.finite_rings.integer_mod.lucas(k, P, Q=1, n=None)

Return $$[V_k(P, Q) \mod n, Q^{\lfloor k/2 \rfloor} \mod n]$$ where $$V_k$$ is the Lucas function defined by the recursive relation

$V_k(P, Q) = P V_{k-1}(P, Q) - Q V_{k-2}(P, Q)$

with $$V_0 = 2, V_1 = P$$.

INPUT:

• k – integer; index to compute
• P, Q – integers or modular integers; initial values
• n – integer (optional); modulus to use if P is not a modular integer

REFERENCES:

 [IEEEP1363] IEEE P1363 / D13 (Draft Version 13). Standard Specifications for Public Key Cryptography Annex A (Informative). Number-Theoretic Background. Section A.2.4

AUTHORS:

• Somindu Chaya Ramanna, Shashank Singh and Srinivas Vivek Venkatesh (2011-09-15, ECC2011 summer school)

EXAMPLES:

sage: [lucas(k,4,5,11)[0] for k in range(30)]
[2, 4, 6, 4, 8, 1, 8, 5, 2, 5, 10, 4, 10, 9, 8, 9, 7, 5, 7, 3, 10, 3, 6, 9, 6, 1, 7, 1, 2, 3]

sage: lucas(20,4,5,11)
[10, 1]

sage.rings.finite_rings.integer_mod.lucas_q1(mm, P)

Return $$V_k(P, 1)$$ where $$V_k$$ is the Lucas function defined by the recursive relation

$$V_k(P, Q) = PV_{k-1}(P, Q) - QV_{k-2}(P, Q)$$

with $$V_0 = 2, V_1(P_Q) = P$$.

REFERENCES:

 [Pos88] H. Postl. ‘Fast evaluation of Dickson Polynomials’ Contrib. to General Algebra, Vol. 6 (1988) pp. 223-225

AUTHORS:

sage.rings.finite_rings.integer_mod.makeNativeIntStruct

alias of NativeIntStruct

sage.rings.finite_rings.integer_mod.mod(n, m, parent=None)

Return the equivalence class of $$n$$ modulo $$m$$ as an element of $$\ZZ/m\ZZ$$.

EXAMPLES:

sage: x = Mod(12345678, 32098203845329048)
sage: x
12345678
sage: x^100
1017322209155072

You can also use the lowercase version:

sage: mod(12,5)
2

Illustrates that trac ticket #5971 is fixed. Consider $$n$$ modulo $$m$$ when $$m = 0$$. Then $$\ZZ/0\ZZ$$ is isomorphic to $$\ZZ$$ so $$n$$ modulo $$0$$ is equivalent to $$n$$ for any integer value of $$n$$:

sage: Mod(10, 0)
10
sage: a = randint(-100, 100)
sage: Mod(a, 0) == a
True

sage.rings.finite_rings.integer_mod.square_root_mod_prime(a, p=None)

Calculates the square root of $$a$$, where $$a$$ is an integer mod $$p$$; if $$a$$ is not a perfect square, this returns an (incorrect) answer without checking.

ALGORITHM: Several cases based on residue class of $$p \bmod 16$$.

• $$p \bmod 2 = 0$$: $$p = 2$$ so $$\sqrt{a} = a$$.
• $$p \bmod 4 = 3$$: $$\sqrt{a} = a^{(p+1)/4}$$.
• $$p \bmod 8 = 5$$: $$\sqrt{a} = \zeta i a$$ where $$\zeta = (2a)^{(p-5)/8}$$, $$i=\sqrt{-1}$$.
• $$p \bmod 16 = 9$$: Similar, work in a bi-quadratic extension of $$\GF{p}$$ for small $$p$$, Tonelli and Shanks for large $$p$$.
• $$p \bmod 16 = 1$$: Tonelli and Shanks.

REFERENCES:

• Siguna Muller. ‘On the Computation of Square Roots in Finite Fields’ Designs, Codes and Cryptography, Volume 31, Issue 3 (March 2004)
• A. Oliver L. Atkin. ‘Probabilistic primality testing’ (Chapter 30, Section 4) In Ph. Flajolet and P. Zimmermann, editors, Algorithms Seminar, 1991-1992. INRIA Research Report 1779, 1992, http://www.inria.fr/rrrt/rr-1779.html. Summary by F. Morain. http://citeseer.ist.psu.edu/atkin92probabilistic.html
• H. Postl. ‘Fast evaluation of Dickson Polynomials’ Contrib. to General Algebra, Vol. 6 (1988) pp. 223-225

AUTHORS:

sage: from sage.rings.finite_rings.integer_mod import square_root_mod_prime   # sqrt() uses brute force for small p
sage: all([square_root_mod_prime(a*a)^2 == a*a
....:      for p in prime_range(100)
....:      for a in Integers(p)])
True

sage.rings.finite_rings.integer_mod.square_root_mod_prime_power(a, p, e)

Calculates the square root of $$a$$, where $$a$$ is an integer mod $$p^e$$.

ALGORITHM: Perform $$p$$-adically by stripping off even powers of $$p$$ to get a unit and lifting $$\sqrt{unit} \bmod p$$ via Newton’s method.

AUTHORS:

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod import square_root_mod_prime_power
sage: a=Mod(17,2^20)
sage: b=square_root_mod_prime_power(a,2,20)
sage: b^2 == a
True

sage: a=Mod(72,97^10)
sage: b=square_root_mod_prime_power(a,97,10)
sage: b^2 == a
True
sage: mod(100, 5^7).sqrt()^2
100


text:
# Codeforces 1615G. Maximum Adjacent Pairs (3300)

Posted by JustinK101 on Sun, 02 Jan 2022 18:47:24 +0100

Given the sequence \ (a \) with length \ (n \), the values of some positions in \ (a \) have been determined, and the values of others have not been determined. The number at these positions is \ (0 \), which needs to be replaced with the value of \ (1\sim n \).
Fill in all positions with \ (0 \) so that the number of \ (k(k\in [1,n]) \) meeting the following conditions is the largest, and construct any scheme.

• $$\exists i\in [1,n)$$，$$a_i=a_{i+1}=k$$.

$$2\le n\le 3\cdot 10^5,0\le a_i\le \min(n,600)$$.

In my lifetime, I came up with a question \ (\) on the field, but I didn't finish it \ () \).

$$\color{green}{\text{observation:}}$$
Considering that the valued part will divide the whole sequence into several segments, only the position of uncertain value adjacent to the valued position can match it.
Consider an interval \ ([l,r] \) with a length of \ (len \) and all \ (0 \), and discuss the parity of \ (len \).

• If \ (len \) is an odd number, it must be possible to match two pairs of \ (len-1 \), and the remaining one can match either \ (a {L-1} \) or \ (a {R + 1} \). According to the greedy strategy, this must be optimal. Assuming that both \ (a {L-1} \) and \ (a {R + 1} \) match, the maximum contribution is \ (2+\lfloor \frac{len-2}{2}\rfloor=\frac{len+1}{2} \), while the maximum contribution of the former is \ (1+\lfloor \frac{len-1}{2}\rfloor=\frac{len+1}{2} \). The maximum contribution is the same, but the latter two may not match with others. If the former can match, the latter must also match. Therefore, the contribution of the latter is always \ (\ ge \) the contribution of the former.
• If \ (len \) is even, there are only two cases. One is that both \ (a {L-1} \) and \ (a {R + 1} \) match, and the middle \ (len-2 \) match in pairs. The other is to match the middle \ (len \) directly regardless of the on both sides. According to the greedy strategy, these two can cover all situations. Although the former scheme has the greatest contribution, it may affect other matching, so both should be considered.

Then you can naturally think of using it General graph maximum matching Algorithm to solve.

Consider connecting edges.

• If \ (len \) is an odd number, connect \ (a {L-1} \) to a new point \ (v \), and \ (a {R + 1} \) to a new point \ (v \). Then \ (v \) can only match one of them.

• If \ (len \) is even, connect \ (a {L-1} \) to a new point \ (v 1 \), \ (a {R + 1} \) to a new point \ (V 2 \), and then connect \ (v 1 \) and \ (V 2 \). This just corresponds to the two cases discussed. If \ (a {L-1} \) and \ (v 1 \) are connected, and \ (a {R + 1} \) and \ (V 2 \) are connected, then both sides are matched; Otherwise, if \ (v_1 \) and \ (v_2 \) are connected, both sides do not match.

$$\color{blue}{\text{code}}$$

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N = 6e5 + 5, M = 12e5 + 5;
int n, a[N], id = 1, have[N], head[N], tot, ver[M], nxt[M];
int fa[N], vis[N], pre[N], match[N], dfn[N], timer; bool del[M], vs[N];
queue <int> q; vector <int> clr; vector < pair<int, int> > vec;
inline void add(int u, int v) {
}
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline int lca(int u, int v) {
timer ++, u = find(u), v = find(v);
while(dfn[u] != timer) {
dfn[u] = timer;
u = find(pre[match[u]]);
if(v) u ^= v ^= u ^= v;
}
return u;
}
inline void blossom(int x, int y, int z) {
while(find(x) != z) {
pre[x] = y; y = match[x];
if(vis[y] == 2) vis[y] = 1, q.push(y), clr.eb(y);
if(x == find(x)) fa[x] = z;
if(y == find(y)) fa[y] = z;
x = pre[y];
}
}
inline bool bfs(int s) {
for (auto x : clr) vis[x] = pre[x] = 0, fa[x] = x; clr.clear();
while(!q.empty()) q.pop();
q.push(s); vis[s] = 1; clr.eb(s);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if(vis[v] == 2 || find(u) == find(v)) continue;
if(vis[v] == 0) {
vis[v] = 2; pre[v] = u; clr.eb(v);
if(!match[v]) {
for(int x = v, lst; x; x = lst) {
lst = match[pre[x]];
match[x] = pre[x];
match[pre[x]] = x;
}
return 1;
}
vis[match[v]] = 1;
q.push(match[v]);
clr.eb(match[v]);
}
else {
int w = lca(u, v);
blossom(u, v, w); blossom(v, u, w);
clr.eb(v), clr.eb(w);
}
}
}
return 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n + n; ++ i) fa[i] = i;
for (int i = 1; i <= n; ++ i) scanf("%d", a + i), have[a[i]] = 1;
for (int i = 1; i < n; ++ i) if (a[i] == a[i - 1] && a[i]) vs[a[i]] = 1;
for (int i = 1, j; i <= n; i = j + 1) {
j = i; if (a[i]) continue;
while (!a[j] && j <= n) ++ j;
vec.emplace_back(i, j);
if ((j - i) & 1) {
if (i > 1 && !vs[a[i - 1]]) add(a[i - 1], n + i);
if (j <= n && !vs[a[j]]) add(a[j], n + i);
} else {
if (i > 1 && !vs[a[i - 1]]) add(a[i - 1], n + i);
if (j <= n && !vs[a[j]]) add(a[j], n + j - 1);
add(n + i, n + j - 1);
}
}
for (int i = 1; i <= n + n; ++ i) if (!match[i]) bfs(i);
for (auto p : vec) {
int l = p.first, r = p.second;
if ((r - l) & 1) {
if (l > 1 && match[n + l] == a[l - 1]) {
a[l] = a[l - 1];
for (int i = l + 1; i + 1 < r; i += 2) {
while (have[id]) ++ id;
a[i] = a[i + 1] = id ++;
}
} else {
for (int i = l; i + 1 < r; i += 2) {
while (have[id]) ++ id;
a[i] = a[i + 1] = id ++;
}
a[r - 1] = a[r];
}
} else {
if (match[n + l] == n + r - 1) {
for (int i = l; i + 1 < r; i += 2) {
while (have[id]) ++ id;
a[i] = a[i + 1] = id ++;
}
} else {
a[l] = a[l - 1], a[r - 1] = a[r];
for (int i = l + 1; i + 1 < r; i += 2) {
while (have[id]) ++ id;
a[i] = a[i + 1] = id ++;
}
}
}
}
for (int i = 1; i <= n; ++ i) printf("%d ", a[i] ? a[i] : 1);
return 0;
}